結果
問題 | No.1149 色塗りゲーム |
ユーザー |
![]() |
提出日時 | 2020-08-07 22:18:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 141 ms / 2,000 ms |
コード長 | 1,749 bytes |
コンパイル時間 | 2,625 ms |
コンパイル使用メモリ | 202,548 KB |
最終ジャッジ日時 | 2025-01-12 17:09:13 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <bits/stdc++.h> using namespace std; using Int = long long; const char newl = '\n'; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);} template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } //INSERT ABOVE HERE signed paint(int k,int x){ cout<<k<<' '<<x+1<<endl; int t; cin>>t; return t; } signed main(){ int n; cin>>n; vector<int> gs(n+1,0); gs[0]=0; for(int i=1;i<=n;i++){ set<int> ss; // place one for(int j=0;j<i;j++) ss.emplace(gs[j]^gs[i-(j+1)]); // place two for(int j=0;j+1<i;j++) ss.emplace(gs[j]^gs[i-(j+2)]); while(ss.count(gs[i])) gs[i]++; } auto calc=[&](auto vs){ vs.emplace_back(1); int res=0,cur=0; for(int v:vs){ if(v==1) res^=gs[cur],cur=0; if(v==0) cur++; } return res; }; vector<int> st(n,0); auto play=[&](){ int k,x; cin>>k>>x; x--; for(int i=0;i<k;i++) st[x+i]=1; }; while(1){ int flg=0; for(int i=0;i<n;i++){ if(st[i]!=0) continue; st[i]=1; if(calc(st)!=0){ st[i]=0; continue; } int t=paint(1,i); if(t==0) return 0; flg=1; play(); break; } if(flg) continue; for(int i=0;i+1<n;i++){ if(st[i+0]!=0 or st[i+1]!=0) continue; st[i+0]=st[i+1]=1; if(calc(st)!=0){ st[i+0]=st[i+1]=0; continue; } int t=paint(2,i); if(t==0) return 0; flg=1; play(); break; } assert(flg); } return 0; }