yukicoder : No.2496 LCM between Permutations

コーナーケース対応が大変。
https://yukicoder.me/problems/no/2496

問題

整数Nが与えられる。
1～NのPermutation 2個A,Bの内容を当てるinteractive問題である。
2要素A[i],B[j]を指定し、そのLCMを答えるクエリを最大3N回用いて、A,Bを特定せよ。

解法

N/2より大きな素数pを考えると、LCMがpの倍数である場合、A[i]とB[j]のいずれかが
A[i]=pとなるiが見つかれば、1とp以外の値を取るBを特定できる。
また、その時LCM(A[i],B[x])=LCM(A[i],B[y])=pとなるx,yがあればB[x]とB[y]のどちらかが1,pである。
これはA[i+1]などとLCMを取れば確定できる。

こうして1を1か所特定すれば、あと(2N-1)クエリで全要素列挙できる。

int N;
int A[2020],B[2020];

int ask(int a,int b) {
	cout<<"? "<<a+1<<" "<<b+1<<endl;
	cin>>a;
	return a;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N==1) {
		cout<<"! 1 1"<<endl;
		return;
	}
	
	int piv;
	for(i=N;i>=1;i--) {
		for(x=2;x<i;x++) if(i%x==0) break;
		if(x==i) {
			piv=i;
			break;
		}
		
	}
	
	vector<int> C;
	FOR(i,N) {
		B[i]=ask(0,i);
		if(B[i]%piv==0) C.push_back(i);
	}
	
	if(C.size()>1) {
		C.clear();
		FOR(i,N) {
			B[i]/=piv;
			if(B[i]==1) C.push_back(i);
		}
		x=ask(1,C[0]);
		y=ask(1,C[1]);
		if(x<y) {
			B[C[1]]=piv;
			x=C[0];
		}
		else {
			B[C[0]]=piv;
			x=C[1];
		}
		FOR(i,N) A[i]=ask(i,x);
	}
	else {
		x=C[0];
		C.clear();
		FOR(i,N) {
			A[i]=ask(i,x)/piv;
			if(A[i]==1) C.push_back(i);
		}
		x=ask(C[0],(x+1)%N);
		if(x%piv) {
			A[C[1]]=piv;
			x=C[0];
		}
		else {
			A[C[0]]=piv;
			x=C[1];
		}
		
		FOR(i,N) {
			vector<int> V;
			for(j=1;j<=N;j++) if(A[0]*j/__gcd(A[0],j)==B[i]) V.push_back(j);
			if(V.size()==1) {
				B[i]=V[0];
			}
			else {
				B[i]=ask(x,i);
			}
		}
		
		
	}
	cout<<"!";
	FOR(i,N) cout<<" "<<A[i];
	FOR(i,N) cout<<" "<<B[i];
	cout<<endl;
	
}

まとめ

解法はすぐ思いついたものの、最初3Nクエリをちょっと超えちゃって手間取った。