Codeforces #865 : Div1 B. Sum Graph

やらかした回。
https://codeforces.com/contest/1815/problem/B

問題

1～NのPermutation Pを当てるInteractive問題。
以下のクエリを計2N回まで使い、Pを２つに絞れ。

1～Nの頂点ラベルを持つ無向グラフを考える。

• 整数Xを与えると、u+v=Xとなる２頂点u,v間に辺が張られる。
• i,jを指定すると、P[i]とP[j]の最短距離が与えられる。

解法

X=N+1,N+2で2回辺を張ると、直線状のグラフになる。
ここに前者のクエリを(N-1)回たたくと、グラフの直径を成す２点の片方、すなわちP[i]=1またはP[i]=Nとなるiが求められる。
あとはP[i]とP[j]の距離を求めれば、P[j]の値も(P[i]によって)2値のいずれか確定する。

int T,N;
int P[2][1101];
void type1(int v) {
	cout<<"+ "<<v+2<<endl;
	cin>>v;
	assert(v==1);
}
int type2(int i,int j) {
	cout<<"? "<<i+1<<" "<<j+1<<endl;
	cin>>i;
	return i;
}

void ans() {
	cout<<"!";
	int i,j;
	FOR(i,2) {
		FOR(j,N) cout<<" "<<P[i][j];
	}
	cout<<endl;
	cin>>i;
	assert(i==1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		MINUS(P);
		type1(N-1);
		type1(N-2);
		int ma=1;
		int D[1010];
		for(i=1;i<N;i++) {
			D[i]=type2(0,i);
			if(D[i]>D[ma]) ma=i;
		}
		FOR(i,N) if(i!=ma) {
			D[i]=type2(ma,i);
		}
		
		vector<int> cand;
		for(int L=1,R=N;L<=R;L++,R--) {
			cand.push_back(R);
			cand.push_back(L);
		}
		
		D[ma]=0;
		FOR(i,N) {
			P[0][i]=cand[D[i]];
			P[1][i]=cand[N-1-D[i]];
		}
		ans();
		
		
	}
}

まとめ

本番やけにてこずってるな…。