【1】做题心得 - 2025 NOIP #67 - T3【Ad-hoc】

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=5;
int n,d,k,a[N][5],l,r,ma;
int t[M*N],tc;
int vis[N*M];
void dfs(int p,int flg,int len){
	if(p>n){
		if(len>ma){
			ma=len;
			l=p-len+1,r=p-1;
		}
		return;
	}
	int has=0;
	for(int i=1;i<=d;i++)if(vis[a[p][i]]==1)
		{ has=1;break; }
	if(has){ dfs(p+1,flg,len+1);return; }
	if(!has&&flg==k){
		if(len>ma){
			ma=len;
			l=p-len+1,r=p-1;
		}
		return;
	}
	for(int i=1;i<=d;i++)if(vis[a[p][i]]!=-1){
		vis[a[p][i]]=1;
		dfs(p+1,flg+1,len+1);
		vis[a[p][i]]=0;
	}
	return;
}
int main(){
	freopen("meow.in","r",stdin);
	freopen("meow.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=d;j++) cin>>a[i][j], t[++tc]=a[i][j];
	sort(t+1,t+tc+1);
	tc=unique(t+1,t+tc+1)-t-1;
	for(int i=1;i<=n;i++)for(int j=1;j<=d;j++)	
		a[i][j]=lower_bound(t+1,t+tc+1,a[i][j])-t;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=d;j++) vis[a[i-1][j]]=-1;
		dfs(i,0,1);
		for(int j=1;j<=d;j++) vis[a[i-1][j]]= 0;
	}
	cout<<l<<" "<<r;
	return 0;
}