結果
問題 |
No.850 企業コンテスト2位
|
ユーザー |
![]() |
提出日時 | 2019-07-05 23:07:54 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,881 bytes |
コンパイル時間 | 1,370 ms |
コンパイル使用メモリ | 90,744 KB |
実行使用メモリ | 25,476 KB |
平均クエリ数 | 260.79 |
最終ジャッジ日時 | 2024-07-16 17:33:20 |
合計ジャッジ時間 | 6,905 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 WA * 17 |
ソースコード
#include<iostream> #include<algorithm> #include<vector> #include<string> #include<set> #include<queue> #include<stack> #include<bitset> using namespace std; int p = 1000000007; #define int long long #define vel vector<long long> #define vvel vector<vel> #define rep(i,n) for(long long i=0;i<n;i++) #define sor(v) sort(v.begin(),v.end()) #define mmax(a,b) a=max(a,b) #define mmin(a,b) a=min(a,b) #define mkp make_pair #define pin pair<int,int> #define V vector #define Endl endl #define veb vector<bool> #define sq(a) (a)*(a) #define rev(s) reverse(s.begin(),s.end()) #define end_program(s) cout << s <<endl;return 0 int kai_size = 120001; vel kai(kai_size, 1); vel ink(kai_size, 1); vel dist; int RE() { vel v(3, 2); return v.at(4); } int ru(int a, int r) { if (r == 0) { return 1; } int ans = ru(a, r / 2); ans *= ans; ans %= p; if (r % 2 == 1) { ans *= a; } return ans % p; } int inv(int a) { return ru(a, p - 2); } void make_kai() { rep(i, kai_size-1) { kai[i + 1] = (kai[i] * (i + 1)) % p; } rep(i, kai_size) { ink[i] = inv(kai[i]); } } int com(int n, int r) { int ans = kai[n] * ink[r]; ans %= p; ans *= ink[n - r]; ans %= p; return ans; } vel dis(int mid1, vvel &way) { int n = way.size(); vel dist(n, -1); dist[mid1] = 0; queue<int> q; q.push(mid1); while (!q.empty()) { int st = q.front(); q.pop(); rep(i, way[st].size()) { int to = way[st][i]; if (dist[to] == -1) { dist[to] = dist[st] + 1; q.push(to); } } } return dist; } pin most_far(int now, int n, vvel &way) { vel dist1 = dis(now, way); pin ans = mkp(-1, 0); rep(i, n) { if (dist1[i] > ans.first) { ans = mkp(dist1[i], i); } } return ans; } int gcd(int a, int b) { a = abs(a); b = abs(b); if (a < b) { swap(a, b); } if (b == 0) { return a; } return gcd(b, a%b); } int per(int a, int b) { int ans = a % b; if (ans < 0) { ans += b; } return ans; } V<pin> uni(V<pin> &v) { sor(v); V<pin> ans(1, v[0]); for (int i = 1; i < v.size(); i++) { if (v[i] != v[i-1]) { ans.push_back(v[i]); } } v = ans; return v; } int N; int ask(int a, int b) { if (a > N) { return b; } if (b > N) { return a; } cout << "? " << a << " " << b<<endl<<flush; int ans; cin >> ans; return ans; } signed main() { cin >> N; int n = 300; vvel ans(n / 2, vel(2)); rep(i, n) { ans[i / 2][i % 2] = i+1; } rep(i, n / 2) { if (ask(ans[i][0], ans[i][1]) == ans[i][1]) { swap(ans[i][0], ans[i][1]); } } while (ans.size() > 1) { vvel qans(ans.size()/2,vel(2)); rep(i, ans.size() / 2) { qans[i][0] = ask(ans[2 * i][0], ans[2 * i + 1][0]); if (qans[i][0]==ans[2 * i][0]) { ans[2 * i] = { ans[2 * i][1] }; } else { ans[2 * i + 1] = { ans[2 * i + 1][1] }; } qans[i][1] = ask(ans[2 * i][0], ans[2 * i + 1][0]); } if (ans.size() % 2 == 1) { qans.push_back(ans[ans.size() - 1]); } ans = qans; } cout << "! " << ans[0][1]; return 0; }