結果
問題 | No.2496 LCM between Permutations |
ユーザー |
|
提出日時 | 2023-10-09 13:30:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 3,080 bytes |
コンパイル時間 | 1,414 ms |
コンパイル使用メモリ | 112,944 KB |
実行使用メモリ | 25,448 KB |
平均クエリ数 | 776.38 |
最終ジャッジ日時 | 2024-07-26 18:31:47 |
合計ジャッジ時間 | 4,756 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:95:26: warning: 'b' may be used uninitialized [-Wmaybe-uninitialized] 95 | A[a]=B[b]=1; | ~~~~^~ main.cpp:85:23: note: 'b' was declared here 85 | int a,b; | ^ main.cpp:95:21: warning: 'a' may be used uninitialized [-Wmaybe-uninitialized] 95 | A[a]=B[b]=1; | ~~~~^~~~~~~ main.cpp:85:21: note: 'a' was declared here 85 | int a,b; | ^
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<map> #include<cassert> #include<cstdlib> using namespace std; const bool debug=false; int gcd(int a,int b) { while(b) { int t=a%b; a=b; b=t; } return a; } bool isp[1001]; int N; int A[1000],B[1000]; int aA[1000],aB[1000]; int ask(int i,int j) { cout<<"? "<<i+1<<" "<<j+1<<endl; if(debug)return aA[i]*aB[j]/gcd(aA[i],aB[j]); int x;cin>>x; return x; } void answer() { cout<<"!"; for(int i=0;i<N;i++)cout<<" "<<A[i]; for(int i=0;i<N;i++)cout<<" "<<B[i]; cout<<endl; if(debug) { for(int i=0;i<N;i++)if(aA[i]!=A[i]||aB[i]!=B[i]) { cout<<"WA"<<endl; exit(1); } cout<<"AC"<<endl; } exit(0); } #include<random> mt19937 rng; void setup() { random_device seed_gen; unsigned int seed=seed_gen(); //seed=1604191338; if(debug)cout<<"seed = "<<seed<<endl; rng=mt19937(seed); if(!debug)return; N=rng()%100+1; for(int i=0;i<N;i++)aA[i]=aB[i]=i+1; shuffle(aA,aA+N,rng); shuffle(aB,aB+N,rng); cout<<"answer ="; for(int i=0;i<N;i++)cout<<" "<<aA[i]; for(int i=0;i<N;i++)cout<<" "<<aB[i]; cout<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); setup(); if(!debug)cin>>N; for(int i=2;i<=N;i++)isp[i]=true; for(int i=2;i<=N;i++)if(isp[i]) { for(int j=i+i;j<=N;j+=i)isp[j]=false; } if(N==1) { A[0]=B[0]=1; answer(); } if(N==2) { bool fn=false; int a,b; for(int i=0;!fn&&i<2;i++)for(int j=0;!fn&&j<2;j++) { if(ask(i,j)==1) { a=i,b=j; fn=true; } } A[0]=A[1]=B[0]=B[1]=2; A[a]=B[b]=1; answer(); } int T[1000]; int mini=0; for(int i=0;i<N;i++) { T[i]=ask(0,i); if(T[mini]>T[i])mini=i; } A[0]=T[mini]; map<int,vector<int> >LtoB; for(int b=1;b<=N;b++) { int L=A[0]/gcd(A[0],b)*b; LtoB[L].push_back(b); } vector<pair<int,int> >Ps,nPs; for(int i=0;i<N;i++) { assert(LtoB.find(T[i])!=LtoB.end()); if(LtoB[T[i]].size()==1) { int p=B[i]=LtoB[T[i]][0]; if(isp[p]) { Ps.push_back(make_pair(p,i)); } else { nPs.push_back(make_pair(p,i)); } } } sort(Ps.begin(),Ps.end()); assert(!Ps.empty()); assert(Ps.back().first*3>N); int P=Ps.back().first,Pi=Ps.back().second; for(int i=1;i<N;i++) { int v=ask(i,Pi); assert(v%P==0); A[i]=v/P; } vector<int>one; for(int i=0;i<N;i++)if(A[i]==1)one.push_back(i); assert(one.size()==2); vector<int>test; int ONE; for(int i=0;i<N;i++)if(i!=Pi)test.push_back(i); assert(test.size()>=2); if(ask(one[0],test[0])%P!=0||ask(one[0],test[1])%P!=0)ONE=one[0]; else ONE=one[1]; A[one[0]+one[1]-ONE]=P; for(int i=0;i<N;i++)if(B[i]==0)B[i]=ask(ONE,i); if(P*2<=N) { assert((N==4&&A[0]==3)||(N==6&&A[0]==5)||(N==10&&A[0]==7)); //[4, 3] //{1=>[1, 3], 2=>[2], 4=>[4]} //[6, 5] //{1=>[1, 5], 2=>[2], 3=>[3], 4=>[4], 6=>[6]} //[10, 7] //{1=>[1, 7], 2=>[2], 3=>[3], 4=>[4], 5=>[5], 6=>[6], 8=>[8], 9=>[9], 10=>[10]} vector<int>two; for(int i=0;i<N;i++)if(A[i]==2)two.push_back(i); assert(two.size()==2); int O=0; while(B[O]!=1)O++; if(ask(two[0],O)==2)A[two[1]]=2*P; else A[two[0]]=2*P; } answer(); }