結果
問題 | No.5002 stick xor |
ユーザー |
![]() |
提出日時 | 2018-05-26 00:27:22 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 1,000 ms |
コード長 | 1,874 bytes |
コンパイル時間 | 3,944 ms |
実行使用メモリ | 1,560 KB |
スコア | 851 |
最終ジャッジ日時 | 2018-05-26 00:27:28 |
ジャッジサーバーID (参考情報) |
judge10 / |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include<algorithm> #include<cassert> #include<iostream> #include<vector> #include<random> using namespace std; typedef long long lint; typedef vector<int>vi; typedef pair<int,int>pii; #define rep(i,n)for(int i=0;i<(int)(n);++i) const int K=500; int l[K]; const int N=60; string a[N]; int b[N][N]; int calc_score(const vector<pii>&ans){ int c[N][N]; rep(i,N)rep(j,N)c[i][j]=b[i][j]; rep(i,ans.size()){ if(ans[i].second<0){ assert(ans[i].first+l[i]-1<=N); rep(j,l[i]) c[ans[i].first+j-1][-ans[i].second-1]^=1; } else{ assert(ans[i].second+l[i]-1<=N); rep(j,l[i]) c[ans[i].first-1][ans[i].second+j-1]^=1; } } int t=0; rep(i,N)rep(j,N)t+=1-c[i][j]; return t; } void output(const vector<pii>&ans){ int orig=calc_score(vector<pii>()); rep(i,ans.size()){ if(ans[i].second<0) cout<<ans[i].first<<" "<<-ans[i].second<<" "<<(ans[i].first+l[i]-1)<<" "<<-ans[i].second<<endl; else cout<<ans[i].first<<" "<<ans[i].second<<" "<<ans[i].first<<" "<<(ans[i].second+l[i]-1)<<endl; } int sc=calc_score(ans); cerr<<"orig="<<orig<<endl; cerr<<"scor="<<sc<<endl; cerr<<"diff="<<sc-orig<<endl; } int main(){ int n,k; cin>>n>>k; assert(n==N); assert(k==K); rep(i,k)cin>>l[i]; rep(i,n)cin>>a[i]; rep(i,n)rep(j,n)b[i][j]=a[i][j]=='1'; int ma=-1e8; vector<pii> ans(k); // +:horizontal, -:vertical rep(i,k)ans[i]=pii(1,1); ma=calc_score(ans); mt19937 mt(('k'<<16)^('i'<<15)^('r'<<14)^('i'<<13)^('k'<<12)^('a'<<11)); rep(_,1000){ vector<pii> cur(k); rep(i,k){ bool vert=mt()%2; if(vert){ cur[i].first=mt()%(N-l[i]+1)+1; cur[i].second=mt()%N+1; cur[i].second*=-1; }else{ cur[i].first=mt()%N+1; cur[i].second=mt()%(N-l[i]+1)+1; } } int sc=calc_score(cur); if(sc>ma){ sc=ma; ans=cur; } } //output output(ans); }