yukicoder : No.2967 Nana's Plus Permutation Game

2965より簡単な気がする。
https://yukicoder.me/problems/no/2967

問題

1～NのPermutation Pを当てるリアクティブ問題である。
2つの添え字i,jを指定すると、P[i]+P[j]がN以下ならP[i]+P[j]=P[k]となるkを、Nを超えるなら-1を返すクエリがある。
このクエリを2N回まで使い、Pの全要素を特定せよ。

解法

i,jを同じ値にすると、2*P[i]=P[k]となるiとkの関係が得られる。
倍々を繰り返して-1に至るまでの回数が一番多いiがあれば、それはP[i]=1となる。

P[i]=1がわかれば、2,3,4,....と順次求めて行くことができる。

int N;
int ask(int a,int b) {
	cout<<1<<" "<<a+1<<" "<<b+1<<endl;
	cin>>a;
	if(a>0) a--;
	return a;
}

int nex[5050];
int P[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) nex[i]=ask(i,i);
	
	int d=-1,f=1;
	FOR(i,N) {
		int cur=i;
		int step=0;
		while(cur!=-1) {
			step++;
			cur=nex[cur];
		}
		if(step>d) {
			d=step;
			f=i;
		}
	}
	P[f]=1;
	int pre=f;
	for(i=2;i<=N;i++) {
		x=ask(f,pre);
		P[x]=i;
		pre=x;
	}
	cout<<2;
	FOR(i,N) cout<<" "<<P[i];
	cout<<endl;
	
}

まとめ

Nの上限が10^5とかでもよさそう。