結果

問題 No.1306 Exactly 2 Digits
コンテスト
ユーザー rniya
提出日時 2020-12-06 12:30:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 615 ms / 2,000 ms
コード長 1,785 bytes
コンパイル時間 2,536 ms
コンパイル使用メモリ 206,900 KB
最終ジャッジ日時 2025-01-16 18:22:41
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 123
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:76:22: warning: ‘other’ may be used uninitialized [-Wmaybe-uninitialized]
   76 |             if (query(other,pos[i][0])==calc(ans[other],i)) ans[pos[i][0]]=i;
      |                 ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:60:9: note: ‘other’ was declared here
   60 |     int other;
      |         ^~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int N;

pair<int,int> query(int i,int j){
    cout << "? " << i+1 << ' ' << j+1 << endl;
    int p,q; cin >> p >> q;
    return {p,q};
}

void answer(vector<int> v){
    cout << '!';
    for (int i=0;i<v.size();++i) cout << ' ' << v[i];
    cout << endl;
}

pair<int,int> calc(int i,int j){
    int p=i/N-j/N,q=i%N-j%N;
    if (p>q) swap(p,q);
    return {p,q};
}

vector<pair<int,int>> gen(int x){
    vector<pair<int,int>> res;
    for (int i=N;i<N*N;++i){
        res.emplace_back(calc(x,i));
    }
    sort(res.begin(),res.end());
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    int n=N*N-N;
    vector<int> ans(n,-1);
    vector<pair<int,int>> ret;
    ret.emplace_back(0,0);
    for (int i=1;i<n;++i) ret.emplace_back(query(0,i));

    vector<pair<int,int>> sorted(ret);
    sort(sorted.begin(),sorted.end());
    for (int i=N;i<N*N;++i){
        if (sorted==gen(i)){
            ans[0]=i;
        }
    }

    vector<vector<int>> pos(N*N);
    for (int i=1;i<n;++i){
        for (int j=N;j<N*N;++j){
            if (calc(ans[0],j)==ret[i]){
                pos[j].emplace_back(i);
            }
        }
    }

    int other;
    for (int i=0;i<N*N;++i){
        if (pos[i].size()==1){
            ans[pos[i][0]]=i;
            auto p=calc(ans[0],i);
            if (p.first!=p.second) other=pos[i][0];
        }
    }

    for (int i=0;i<N*N;++i){
        if (pos[i].size()<2) continue;
        if (~ans[pos[i][0]]){
            ans[pos[i][1]]=i;
        } else if (~ans[pos[i][1]]){
            ans[pos[i][0]]=i;
        } else {
            if (query(other,pos[i][0])==calc(ans[other],i)) ans[pos[i][0]]=i;
            else ans[pos[i][1]]=i;
        }
    }

    answer(ans);
}
0