結果
問題 | No.2496 LCM between Permutations |
ユーザー |
|
提出日時 | 2023-10-06 23:05:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 2,955 bytes |
コンパイル時間 | 3,861 ms |
コンパイル使用メモリ | 252,460 KB |
最終ジャッジ日時 | 2025-02-17 05:31:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using ld = long double;//only for atcoder#include<atcoder/all>using namespace atcoder;#define rep(i,l,r) for(ll i=(l); i<(r); i++)#define rrep(i,l,r) for(ll i=(r)-1; i>=(l); i--)#define ALL(c) (c).begin(), (c).end()#define RALL(c) (c).rbegin(), (c).rend()#define REV(c) reverse(ALL(c))#define SORT(c) sort(ALL(c))#define RSORT(c) sort(RALL(c))#define MINV(c) *min_element(ALL(c))#define MAXV(c) *max_element(ALL(c))template <typename TYPE>void print(TYPE vec){rep(i,0,vec.size()){cout << vec[i];if(i == vec.size()-1){cout << endl;}else{cout << " ";}}}using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using VS = vector<string>;using VVS = vector<VS>;using VB = vector<bool>;using VVB = vector<VB>;using VC = vector<char>;using VVC = vector<VC>;using VD = vector<ld>;using VVD = vector<VD>;using P = pair<ll,ll>;using VP = vector<P>;using VVP = vector<VP>;const ll LINF = 2e18;const int INF = 2e9;using mint = modint998244353;//素数判定bool prime(int x){bool sosu = true;if(x <= 1){return false;}for(int j=2; j*j<=x; j++){if(x %j == 0){sosu = false;}}return sosu;}void query(int a, int b){cout << "? " << a << " " << b << endl;}int main(){int N;cin >> N;if(N == 1){cout << "! " << 1 << " " << 1 << endl;return 0;}int K = 0;rep(i,1,N+1){if(prime(i)){K = i;}}VI pos(0);rep(i,0,N){query(1,i+1);int x;cin >> x;if(x % K == 0){pos.push_back(i);}}VI A(N);VI B(N);if(pos.size() == N){A[0] = K;rep(i,0,N){query(1,i+1);int x;cin >> x;B[i] = x / K;}int p = -1;rep(i,0,N){if(B[i] == 1){p = i;break;}}rep(i,1,N){query(i+1,p+1);int x;cin >> x;if(x % K == 0){A[i] = x / K;B[p] = K;}else{A[i] = x;if(i == 1){rep(j,0,N){if(B[j] == 1 && p != j){B[j] = K;}}}}}}else{B[pos[0]] = K;rep(i,0,N){query(i+1,pos[0]+1);int x;cin >> x;A[i] = x / K;}int p = -1;rep(i,0,N){if(A[i] == 1){p = i;break;}}rep(i,0,N){if(i == pos[0]){continue;}query(p+1, i+1);int x;cin >> x;if(x % K == 0){B[i] = x / K;A[p] = K;}else{B[i] = x;if(i == 1){rep(j,0,N){if(A[j] == 1 && p != j){A[j] = K;}}}}}}cout << "! ";rep(i,0,N){cout << A[i] << " ";}print<VI>(B);}