結果
問題 | No.1306 Exactly 2 Digits |
ユーザー |
|
提出日時 | 2020-12-04 15:57:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 4,281 bytes |
コンパイル時間 | 3,032 ms |
コンパイル使用メモリ | 216,852 KB |
最終ジャッジ日時 | 2025-01-16 15:52:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 123 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int ll;int main(){int n; cin >> n;if(n==2){ // 出力周り確認cout << "? 1 2" << endl;int a,b; cin >> a >> b;if(a==-1){cout << "! 2 3" << endl;}else{cout << "! 3 2" << endl;}return 0;}vector<pair<int,int>> v;for(int i=2;i<=n*n-n;i++){cout << "? 1 " << i << endl;int a,b; cin >> a >> b;if(a>b)swap(a,b);v.push_back({a,b});}vector<int> res(n*n-n,-1);set<int> used;{int a=0,b=0,c=0,d=0;vector<int> vv,vvv;for(int i=0;i<v.size();i++){if(v[i].first==0){vv.push_back(v[i].second);}if(v[i].second==0){vvv.push_back(-v[i].first);}}sort(vv.rbegin(), vv.rend());sort(vvv.rbegin(), vvv.rend());if(vv.size()>0){a=vv[0];for(int i=1;i<vv.size();i++){if(vv[i]==vv[i-1]){b=vv[i]; break;}}}if(vvv.size()>0){c=vvv[0];for(int i=1;i<vvv.size();i++){if(vvv[i]==vvv[i-1]){d=vvv[i]; break;}}}int one;if(a+c==n-1 and b+d==n-2){one=a+(b+1)*n;}else if(a+d==n-1 and b+c==n-2){one=a+(b+1)*n;}else{one=b+(a+1)*n;}used.insert(one);res[0]=one;}int cnt=0;auto query=[&](int base,int a,int b)->pair<int,int>{cnt++;a*=-1; b*=-1;int f=base/n,s=base%n;int c=-1;int d=-1;if(1<=f+a and f+a<n){if(0<=s+b and s+b<=n-1){c=(f+a)*n+(s+b);}}if(1<=f+b and f+b<n){if(0<=s+a and s+a<=n-1){d=(f+b)*n+(s+a);}}if(n<=c and c<=n*n-1){if(used.find(c)!=used.end()){c=-1;}}else{c=-1;}swap(c,d);if(n<=c and c<=n*n-1){if(used.find(c)!=used.end()){c=-1;}}else{c=-1;}if(c==d)c=-1;return make_pair(c,d);};int id=-1;int mx=0;for(int i=0;i<v.size();i++){pair<int,int> p=query(res[0],v[i].first,v[i].second);if(p.first==-1 or p.second==-1){if(abs(v[i].first)!=abs(v[i].second)){if(id==-1){id=i+1;mx=max(abs(v[i].first),abs(v[i].second));}else if(mx<max(abs(v[i].first),abs(v[i].second))){id=i+1;mx=max(abs(v[i].first),abs(v[i].second));}}res[i+1]=max(p.first,p.second);used.insert(res[i+1]);}}auto check=[&]()->void{for(int i=0;i<v.size();i++){if(res[i+1]!=-1)continue;pair<int,int> p=query(res[0],v[i].first,v[i].second);if(p.first==-1 or p.second==-1){res[i+1]=max(p.first,p.second);used.insert(res[i+1]);}}};for(int i=0;i<v.size();i++){if(res[i+1]!=-1)continue;pair<int,int> p=query(res[0],v[i].first,v[i].second);if(p.first==-1 or p.second==-1){res[i+1]=max(p.first,p.second);used.insert(res[i+1]);check();}else{cout << "? " << id+1 << " " << i+2 << endl;int a,b; cin >> a >> b;if(a>b)swap(a,b);pair<int,int> pp=query(res[id],a,b);map<int,int> mp;mp[p.first]++; mp[p.second]++; mp[pp.first]++; mp[pp.second]++;for(auto p:mp){if(p.second>1){res[i+1]=p.first;used.insert(p.first);}}}}cout << "!";for(int i:res){cout << " " << i;}cout << endl;}