結果
問題 | No.2165 Let's Play Nim! |
ユーザー |
👑 |
提出日時 | 2022-12-16 00:25:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 1,341 bytes |
コンパイル時間 | 1,753 ms |
コンパイル使用メモリ | 204,940 KB |
最終ジャッジ日時 | 2025-02-09 14:08:01 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; // #define endl '\n' int bit_length(int x){ int c = 1; int i = 0; while(c <= x){ i++; c *= 2; } return i; } void solve(){ int n; cin >> n; vector<int> A(n); int x = 0; vector<set<int>> se(20, set<int>()); for(int i = 0; i < n; i++){ cin >> A[i]; x ^= A[i]; for(int j = 0; j < 20; j++){ if((A[i] >> j) & 1) se[j].insert(i); } } bool turn; if(x == 0){ cout << 0 << endl; turn = false; } else{ cout << 1 << endl; turn = true; } int ret; while(1){ if(turn){ assert(x != 0); int b = bit_length(x) - 1; auto it = se[b].begin(); int i = (*it); int a = A[i]; for(int j = 0; j < 20; j++){ if((a >> j) & 1) se[j].erase(i); } int d = a - (a ^ x); cout << i + 1 << " " << d << endl; cin >> ret; if(ret == -1) return; a -= d; A[i] = a; x = 0; for(int j = 0; j < 20; j++){ if((a >> j) & 1) se[j].insert(i); } } else{ assert(x == 0); int i, k; cin >> i >> k; i--; cin >> ret; if(ret == -1) return; int a = A[i]; for(int j = 0; j < 20; j++){ if((a >> j) & 1) se[j].erase(i); } x ^= a; a -= k; x ^= a; A[i] = a; for(int j = 0; j < 20; j++){ if((a >> j) & 1) se[j].insert(i); } } turn = turn ^ true; } } int main(){ solve(); }