結果

問題 No.2496 LCM between Permutations
ユーザー HaaHaa
提出日時 2023-10-06 22:59:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,225 bytes
コンパイル時間 2,423 ms
コンパイル使用メモリ 188,644 KB
実行使用メモリ 24,360 KB
平均クエリ数 862.21
最終ジャッジ日時 2023-10-06 22:59:51
合計ジャッジ時間 5,991 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
24,336 KB
testcase_01 AC 23 ms
23,688 KB
testcase_02 AC 24 ms
23,688 KB
testcase_03 AC 23 ms
24,000 KB
testcase_04 AC 24 ms
24,336 KB
testcase_05 AC 25 ms
23,604 KB
testcase_06 AC 23 ms
23,376 KB
testcase_07 AC 25 ms
23,376 KB
testcase_08 AC 24 ms
23,556 KB
testcase_09 AC 23 ms
23,616 KB
testcase_10 AC 24 ms
23,664 KB
testcase_11 AC 25 ms
24,036 KB
testcase_12 AC 24 ms
23,640 KB
testcase_13 AC 24 ms
24,252 KB
testcase_14 AC 24 ms
23,496 KB
testcase_15 AC 29 ms
23,796 KB
testcase_16 AC 30 ms
24,324 KB
testcase_17 AC 31 ms
23,400 KB
testcase_18 AC 73 ms
23,604 KB
testcase_19 RE -
testcase_20 AC 77 ms
23,628 KB
testcase_21 AC 67 ms
23,364 KB
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 89 ms
24,312 KB
testcase_25 AC 106 ms
23,592 KB
testcase_26 AC 112 ms
23,400 KB
testcase_27 RE -
testcase_28 AC 119 ms
24,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()
template<typename T> bool chmax(T& x, const T& y){return (x<y)?(x=y,true):false;};
template<typename T> bool chmin(T& x, const T& y){return (x>y)?(x=y,true):false;};
constexpr ll MOD=998244353;
constexpr ll INF=2e18;

int cnt=0;

int ask(int i, int j){
    cnt++;
    cout << "? " << i+1 << " " << j+1 << endl;
    int x; cin >> x;
    return x;
}

int main(){
    int n; cin >> n;
    VI pi(n), qi(n);
    iota(ALL(pi),0);
    iota(ALL(qi),0);
    random_shuffle(ALL(pi));
    random_shuffle(ALL(qi));
    set<int> as, bs;
    for(int i=1;i<=n;i++){
        as.insert(i);
        bs.insert(i);
    }
    VI a(n,-1), b(n,-1);
    VI er;
    int sp=-1, sq=-1;
    while(1){
        VI q;
        int mq=n*n;
        for(auto i:qi){
            int x=ask(pi.back(),i);
            q.push_back(x);
            chmin(mq,x);
            if(x==1){
                sp=pi.back();
                sq=i;
                b[i]=1;
            }
        }
        a[pi.back()]=mq;
        as.erase(mq);
        pi.pop_back();
        map<int,int> mpx;
        REP(i,(int)q.size()){
            if(mpx.find(q[i])==mpx.end())
                mpx[q[i]]=qi[i];
            else
                mpx[q[i]]=-1;
        }
        for(auto i:bs){
            int l=i*mq/__gcd(i,mq);
            if(mpx.find(l)!=mpx.end()){
                if(mpx[l]==-1)
                    continue;
                er.push_back(i);
                b[mpx[l]]=i;
            }
        }
        for(auto i:er) bs.erase(i);
        er.clear();
        VI nqi;
        REP(i,(int)q.size()){
            if(q[i]==mq){
                nqi.push_back(qi[i]);
            }
        }
        swap(qi,nqi);
        if(mq==1)
            break;
        VI p;
        int mp=n*n;
        for(auto i:pi){
            int x=ask(i,qi.back());
            p.push_back(x);
            chmin(mp,x);
            if(x==1){
                sp=i;
                sq=qi.back();
                a[i]=1;
            }
        }
        b[qi.back()]=mp;
        bs.erase(mp);
        qi.pop_back();
        map<int,int> mpy;
        REP(i,(int)p.size()){
            if(mpy.find(p[i])==mpy.end())
                mpy[p[i]]=pi[i];
            else
                mpy[p[i]]=-1;
        }
        for(auto i:as){
            int l=i*mp/__gcd(i,mp);
            if(mpy.find(l)!=mpy.end()){
                if(mpy[l]==-1)
                    continue;
                er.push_back(i);
                a[mpy[l]]=i;
            }
        }
        for(auto i:er) as.erase(i);
        er.clear();
        VI npi;
        REP(i,(int)p.size()){
            if(p[i]==mp){
                npi.push_back(pi[i]);
            }
        }
        swap(pi,npi);
        if(mp==1)
            break;
    }
    REP(i,n){
        if(a[i]==-1)
            a[i]=ask(i,sq);
        if(b[i]==-1)
            b[i]=ask(sp,i);
    }
    //cout << cnt << endl;
    assert(cnt<=n*3);
    cout << "!";
    REP(i,n) cout << " " << a[i];
    REP(i,n) cout << " " << b[i];
    cout << endl;
    return 0;
}
0