結果

問題 No.2496 LCM between Permutations
ユーザー HaaHaa
提出日時 2023-10-06 22:35:47
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,077 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 188,332 KB
実行使用メモリ 24,516 KB
平均クエリ数 854.69
最終ジャッジ日時 2023-10-06 22:35:54
合計ジャッジ時間 5,966 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 RE -
testcase_18 RE -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 RE -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 RE -
testcase_28 RE -
権限があれば一括ダウンロードができます

ソースコード

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);
    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;
            }
        }
        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();
            }
        }
        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);
    }
    assert(cnt<=n*3);
    REP(i,n) cout << a[i] << " \n"[i==n-1];
    REP(i,n) cout << b[i] << " \n"[i==n-1];
    return 0;
}
0