Codeforces #655 Div2 F. Omkar and Modes

これまた変わった問題。
https://codeforces.com/contest/1372/problem/F

問題

昇順の数列Aを当てるinteractive問題。
この数列はK個までしかユニークな値が存在しない。

数列の区間を指定するクエリを実行すると、その中の最頻値とその頻度が与えられる。
このクエリを4K回用いて数列を当てよ。

解法

区間内でいったんクエリを実行し、最頻値Xとその頻度Fを求めよう。
あとは同じ区間で先頭から(F-1)区切りでクエリを再帰的に実行していき、Xの場所を特定する。
Xの位置が特定できたら、あとはXの後の区間をそれぞれ再帰的に処理していく。

int N;
int A[202020];

map<int,int> hist;

pair<int,int> ask(int L,int R) {
	cout<<"? "<<L<<" "<<R<<endl;
	int X,F;
	cin>>X>>F;
	return {X,F};
}

int dfs(int L,int R) {
	if(L>R) return L-1;
	auto p=ask(L,R);
	
	
	int i;
	if(hist.count(p.first)) {
		int NL=R-p.second+1;
		int NR=NL+hist[p.first]-1;
		for(i=NL;i<=NR;i++) A[i]=p.first;
		hist.erase(p.first);
		dfs(L,NL-1);
		return NR;
	}
	else {
		hist[p.first]=p.second;
		while(hist.count(p.first)) {
			L=dfs(L,L+p.second-1)+1;
		}
		return dfs(L,R);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	dfs(1,N);
	
	cout<<"!";
	FOR(i,N) cout<<" "<<A[i+1];
	cout<<endl;
	
	
}

まとめ

これはパッと思いつかないなぁ。