結果

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

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=10005;
const ll inf=1e18;
ll t,n,ans[maxn+5],vis[maxn+5],val[maxn+5];
ll q1[maxn+5],q2[maxn+5],pm[maxn+5],rv[maxn+5];
vector<pair<ll,ll>> p[maxn+5];
ll ask(ll i,ll j){
    ll ret;
    printf("? %lld %lld\n",i,j);
    fflush(stdout);
    scanf("%lld",&ret);
    return ret;
}
void ans_out(){
    ll i;
    printf("! ");
    for(i=1;i<=n;i++){
        printf("%lld%c",ans[i],i==n?'\n':' ');
    }
    fflush(stdout);
}
void bfs(ll st){
    ll i,u,v,w;
    queue<ll> q;
    for(i=1;i<=n;i++) vis[i]=0;
    vis[st]=1;
    val[st]=0;
    q.push(st);
    while(not q.empty()){
        u=q.front();
        q.pop();
        for(i=0;i<p[u].size();i++){
            v=p[u][i].first;
            w=p[u][i].second;
            if(not vis[v]){
                vis[v]=1;
                val[v]=val[u]+w;
                q.push(v);
            }
        }
    }
}
int main(){
    ll i,j,k,res,mn,mx,lambda,mu,ok,cand;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(i=1;i<=n;i++) p[i].clear();
        for(i=2;i<=n;i++){
            res=ask(1,i);
            if(res!=-1){
                p[1].push_back({res,1});
                p[res].push_back({1,-1});
                p[i].push_back({res,1});
                p[res].push_back({i,-1});
            }
            q1[i]=res;
        }
        for(i=1;i<=n;i++){
            if(i==2) continue;
            res=ask(2,i);
            if(res!=-1){
                p[2].push_back({res,1});
                p[res].push_back({2,-1});
                p[i].push_back({res,1});
                p[res].push_back({i,-1});
            }
            q2[i]=res;
        }
        bfs(1);
        mn=inf; mx=-inf;
        for(i=1;i<=n;i++){
            if(val[i]<mn) mn=val[i];
            if(val[i]>mx) mx=val[i];
        }
        lambda=(n-1)/(mx-mn);
        mu=1-mn*lambda;
        ok=1;
        for(i=1;i<=n;i++){
            ans[i]=mu+val[i]*lambda;
            if(ans[i]<1 or ans[i]>n) ok=0;
            rv[ans[i]]=i;
        }
        if(ok){
            cand=-1;
            for(i=2;i<=n;i++){
                if(q1[i]!=-1){
                    if(ans[1]+ans[i]!=ans[q1[i]]) ok=0;
                    else cand=i;
                }
                else{
                    if(ans[1]+ans[i]<=n) ok=0;
                }
            }
            if(cand==-1 and ok){
                res=ask(1,2);
                if(res!=-1){
                    if(ans[1]+ans[2]!=ans[res]) ok=0;
                }
                else{
                    if(ans[1]+ans[2]<=n) ok=0;
                }
            }
        }
        if(not ok){
            lambda=-lambda;
            mu=1-mx*lambda;
            for(i=1;i<=n;i++) ans[i]=mu+val[i]*lambda;
        }
        ans_out();
    }
    return 0;
}
0