結果
問題 | No.2496 LCM between Permutations |
ユーザー |
![]() |
提出日時 | 2023-10-06 23:17:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,079 bytes |
コンパイル時間 | 2,628 ms |
コンパイル使用メモリ | 215,780 KB |
最終ジャッジ日時 | 2025-02-17 05:37:36 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 3 WA * 25 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:114:35: warning: ‘zzz’ may be used uninitialized [-Wmaybe-uninitialized] 114 | cout<<"? "<<i+1<<" "<<zzz+1<<endl; | ^ main.cpp:104:9: note: ‘zzz’ was declared here 104 | int zzz; | ^~~
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=1005,INF=1<<30;vector<int> prime;//i番目の素数bool is_prime[MAX+1];void sieve(int n){for(int i=0;i<=n;i++){is_prime[i]=true;}is_prime[0]=is_prime[1]=false;for(int i=2;i<=n;i++){if(is_prime[i]){prime.push_back(i);for(int j=2*i;j<=n;j+=i){is_prime[j] = false;}}}}int main(){std::ifstream in("text.txt");std::cin.rdbuf(in.rdbuf());cin.tie(0);ios::sync_with_stdio(false);sieve(MAX-2);int N;cin>>N;if(N<=3){vector<vector<int>> res(N,vector<int>(N));for(int a=1;a<=N;a++){for(int b=1;b<=N;b++){cout<<"? "<<a<<" "<<b<<endl;int x;cin>>x;res[a-1][b-1]=x;}}vector<int> P(N);iota(all(P),1);vector<int> Q=P;do{do{vector<vector<int>> ans(N,vector<int>(N));for(int a=1;a<=N;a++){for(int b=1;b<=N;b++){ans[a-1][b-1]=P[a-1]*Q[b-1]/gcd(P[a-1],Q[b-1]);}}if(ans==res){cout<<"!";for(int a:P) cout<<" "<<a;for(int a:Q) cout<<" "<<a;cout<<endl;return 0;}}while(next_permutation(all(Q)));}while(next_permutation(all(P)));}map<vector<int>,int> MA;for(int a=1;a<=N;a++){vector<int> S(N);for(int b=1;b<=N;b++){S[b-1]=a*b/gcd(a,b);}sort(all(S));MA[S]=a;}vector<int> que(N),SS;for(int i=0;i<N;i++){cout<<"? 1 "<<i+1<<endl;int x;cin>>x;que[i]=x;}SS=que;sort(all(SS));int x=MA[SS];int tar=-1;for(int i=1;i<=N;i++){if(is_prime[i]&&i+i>N) tar=i;}int tarlcm=x*tar/gcd(x,tar);int zzz;for(int i=0;i<N;i++){if(que[i]==tarlcm){zzz=i;}}vector<int> P(N),Q(N);for(int i=0;i<N;i++){cout<<"? "<<i+1<<" "<<zzz+1<<endl;int x;cin>>x;for(int j=1;j<=N;j++){if(tar*j/gcd(tar,j)==x) P[i]=j;}}for(int i=0;i<N;i++){if(P[i]==1){for(int j=0;j<N;j++){cout<<"? "<<i+1<<" "<<j+1<<endl;cin>>Q[j];}}}cout<<"!";for(int a:P) cout<<" "<<a;for(int a:Q) cout<<" "<<a;cout<<endl;}