#260371 (C++17) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: 夕叢霧香(ゆうむらきりか)
• 提出日時: 2018-05-26 00:27:22
• 言語: C++17 (gcc 13.2.0 + boost 1.83.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 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	46 ms; 1,560 KB
testcase_01	AC	49 ms; 1,560 KB
testcase_02	AC	48 ms; 1,556 KB
testcase_03	AC	48 ms; 1,560 KB
testcase_04	AC	48 ms; 1,560 KB
testcase_05	AC	48 ms; 1,556 KB
testcase_06	AC	49 ms; 1,556 KB
testcase_07	AC	49 ms; 1,560 KB
testcase_08	AC	50 ms; 1,560 KB
testcase_09	AC	57 ms; 1,560 KB
testcase_10	AC	53 ms; 1,556 KB
testcase_11	AC	62 ms; 1,556 KB
testcase_12	AC	57 ms; 1,556 KB
testcase_13	AC	50 ms; 1,556 KB
testcase_14	AC	51 ms; 1,560 KB
testcase_15	AC	51 ms; 1,556 KB
testcase_16	AC	57 ms; 1,556 KB
testcase_17	AC	52 ms; 1,556 KB
testcase_18	AC	52 ms; 1,560 KB
testcase_19	AC	49 ms; 1,556 KB
testcase_20	AC	49 ms; 1,560 KB
testcase_21	AC	51 ms; 1,560 KB
testcase_22	AC	49 ms; 1,560 KB
testcase_23	AC	51 ms; 1,556 KB
testcase_24	AC	50 ms; 1,556 KB
testcase_25	AC	51 ms; 1,560 KB
testcase_26	AC	51 ms; 1,556 KB
testcase_27	AC	50 ms; 1,560 KB
testcase_28	AC	50 ms; 1,556 KB
testcase_29	AC	48 ms; 1,556 KB
testcase_30	AC	50 ms; 1,560 KB
testcase_31	AC	53 ms; 1,560 KB

ソースコード

#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);
}