結果
問題 | No.850 企業コンテスト2位 |
ユーザー | chocorusk |
提出日時 | 2019-03-23 01:40:32 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,795 bytes |
コンパイル時間 | 794 ms |
コンパイル使用メモリ | 100,872 KB |
実行使用メモリ | 24,396 KB |
平均クエリ数 | 210.29 |
最終ジャッジ日時 | 2023-09-23 16:50:08 |
合計ジャッジ時間 | 3,189 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
24,264 KB |
testcase_01 | AC | 23 ms
23,928 KB |
testcase_02 | AC | 23 ms
24,276 KB |
testcase_03 | AC | 23 ms
23,592 KB |
testcase_04 | AC | 24 ms
24,252 KB |
testcase_05 | AC | 23 ms
23,556 KB |
testcase_06 | AC | 22 ms
23,964 KB |
testcase_07 | AC | 26 ms
23,592 KB |
testcase_08 | AC | 28 ms
24,228 KB |
testcase_09 | AC | 27 ms
24,276 KB |
testcase_10 | AC | 31 ms
23,952 KB |
testcase_11 | AC | 33 ms
23,568 KB |
testcase_12 | AC | 33 ms
23,352 KB |
testcase_13 | AC | 32 ms
23,508 KB |
testcase_14 | AC | 31 ms
23,976 KB |
testcase_15 | AC | 31 ms
24,288 KB |
testcase_16 | AC | 31 ms
23,340 KB |
testcase_17 | AC | 33 ms
23,964 KB |
testcase_18 | AC | 31 ms
23,796 KB |
testcase_19 | AC | 34 ms
23,520 KB |
testcase_20 | AC | 33 ms
23,304 KB |
testcase_21 | AC | 33 ms
24,276 KB |
testcase_22 | AC | 32 ms
23,760 KB |
testcase_23 | AC | 31 ms
24,252 KB |
testcase_24 | AC | 34 ms
24,396 KB |
testcase_25 | AC | 35 ms
23,340 KB |
testcase_26 | AC | 36 ms
23,328 KB |
testcase_27 | AC | 23 ms
23,628 KB |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; int main() { int n; cin>>n; int d=1; while(d*d<n) d++; vector<int> v[20]; for(int i=1; i<=n; i++){ v[i%d].push_back(i); } int mxb[20]; int ret; for(int i=0; i<d; i++){ mxb[i]=v[i][0]; for(int j=1; j<v[i].size(); j++){ cout<<"? "<<v[i][j]<<" "<<mxb[i]<<endl; cin>>ret; if(ret==v[i][j]) mxb[i]=v[i][j]; } } int mx=mxb[0], mx2=mxb[1]; int mxi=0; cout<<"? "<<mxb[0]<<" "<<mxb[1]<<endl; cin>>ret; if(ret==mxb[1]){ swap(mx, mx2); mxi=1; } for(int i=2; i<d; i++){ cout<<"? "<<mx2<<" "<<mxb[i]<<endl; cin>>ret; if(ret==mx2) continue; cout<<"? "<<mx<<" "<<mxb[i]<<endl; cin>>ret; if(ret==mxb[i]){ mx2=mx; mx=mxb[i]; mxi=i; }else{ mx2=mxb[i]; } } if(v[mxi].size()==1){ cout<<"! "<<mx2<<endl; return 0; } int mx22=v[mxi][0]; if(mx22==mx) mx22=v[mxi][1]; for(int j=1; j<v[mxi].size(); j++){ if(v[mxi][j]==mx || v[mxi][j]==mx22) continue; cout<<"? "<<mx22<<" "<<v[mxi][j]<<endl; cin>>ret; if(ret==v[mxi][j]) mx22=v[mxi][j]; } cout<<"? "<<mx2<<" "<<mx22<<endl; cin>>ret; cout<<"! "<<ret<<endl; return 0; }