結果

問題 No.3400 Nana's Plus Permutation Game (7 + 7) ÷ 7
コンテスト
ユーザー Mike scarf
提出日時 2025-12-12 16:36:19
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 2,553 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,112 ms
コンパイル使用メモリ 288,584 KB
実行使用メモリ 26,468 KB
平均クエリ数 43041.87
最終ジャッジ日時 2025-12-12 16:37:27
合計ジャッジ時間 61,932 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 77
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int ask(long long int, long long int)’:
main.cpp:12:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |     scanf("%lld",&res);
      |     ~~~~~^~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:18:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   18 |     scanf("%lld",&t);
      |     ~~~~~^~~~~~~~~~~
main.cpp:20:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   20 |         scanf("%lld",&n);
      |         ~~~~~^~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=20005;
ll ans[maxn+5],nxt[maxn+5];
bool elim[maxn+5];
vector<ll> s,next_s;
ll ask(ll i,ll j){
    printf("1 %lld %lld\n",i,j);
    fflush(stdout);
    ll res;
    scanf("%lld",&res);
    return res;
}
int main(){
    ll t,n,i,j,k,res,u,v,cnt;
    mt19937 rng(1337);
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++) elim[i]=false,ans[i]=0;
        s.clear();
        for(i=1;i<=n;i++) s.push_back(i);
        while(s.size()>2){
            shuffle(s.begin(),s.end(),rng);
            next_s.clear();
            vector<pair<ll,ll>> pairs;
            for(i=0;i+1<s.size();i+=2) pairs.push_back({s[i],s[i+1]});
            if(s.size()%2==1) next_s.push_back(s.back());
            bool progress=false;
            for(auto p:pairs){
                if(elim[p.first] or elim[p.second]){
                    if(!elim[p.first]) next_s.push_back(p.first);
                    if(!elim[p.second]) next_s.push_back(p.second);
                    continue;
                }
                res=ask(p.first,p.second);
                if(res!=-1){
                    if(!elim[res]){
                        elim[res]=true;
                        progress=true;
                    }
                    next_s.push_back(p.first);
                    next_s.push_back(p.second);
                }else{
                    next_s.push_back(p.first);
                    next_s.push_back(p.second);
                }
            }
            s.clear();
            for(auto x:next_s) if(!elim[x]) s.push_back(x);
            if(!progress and s.size()>2) break;
        }
        ll node1=-1,node2=-1;
        if(s.size()==2){
            node1=s[0];node2=s[1];
        }else{
            ll p1=s[0],p2=s[1],p3=s[2];
            ll r1=ask(p1,p2),r2=ask(p1,p3);
            if(r1!=-1){node1=p1;node2=p2;}
            else if(r2!=-1){node1=p1;node2=p3;}
            else{node1=p2;node2=p3;}
        }
        ll A=node1,B=node2;
        ll C=ask(A,B);
        ll X=ask(A,C);
        ll Y=ask(B,C);
        ll Z=ask(A,X);
        ll real_1,real_2;
        if(Y==Z){real_1=A;real_2=B;}
        else{real_1=B;real_2=A;}
        ans[real_1]=1;ans[real_2]=2;
        ll cur=real_2;
        for(i=3;i<=n;i++){
            ll nxt_val=ask(real_1,cur);
            ans[nxt_val]=i;
            cur=nxt_val;
        }
        printf("2");
        for(i=1;i<=n;i++) printf(" %lld",ans[i]);
        printf("\n");
        fflush(stdout);
    }
    return 0;
}
0