結果

問題 No.5002 stick xor
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2018-05-26 01:19:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 869 ms / 1,000 ms
コード長 2,515 bytes
コンパイル時間 29,109 ms
実行使用メモリ 1,592 KB
スコア 30,623
最終ジャッジ日時 2018-05-26 01:20:26
ジャッジサーバーID
（参考情報） 		judge10 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 812 ms
1,588 KB
testcase_01 AC 787 ms
1,592 KB
testcase_02 AC 854 ms
1,592 KB
testcase_03 AC 799 ms
1,588 KB
testcase_04 AC 818 ms
1,592 KB
testcase_05 AC 825 ms
1,592 KB
testcase_06 AC 774 ms
1,588 KB
testcase_07 AC 833 ms
1,592 KB
testcase_08 AC 791 ms
1,592 KB
testcase_09 AC 856 ms
1,592 KB
testcase_10 AC 803 ms
1,588 KB
testcase_11 AC 851 ms
1,592 KB
testcase_12 AC 869 ms
1,588 KB
testcase_13 AC 772 ms
1,592 KB
testcase_14 AC 831 ms
1,592 KB
testcase_15 AC 759 ms
1,592 KB
testcase_16 AC 851 ms
1,592 KB
testcase_17 AC 835 ms
1,588 KB
testcase_18 AC 792 ms
1,592 KB
testcase_19 AC 824 ms
1,588 KB
testcase_20 AC 784 ms
1,588 KB
testcase_21 AC 850 ms
1,588 KB
testcase_22 AC 785 ms
1,592 KB
testcase_23 AC 836 ms
1,592 KB
testcase_24 AC 815 ms
1,592 KB
testcase_25 AC 828 ms
1,592 KB
testcase_26 AC 853 ms
1,592 KB
testcase_27 AC 803 ms
1,588 KB
testcase_28 AC 852 ms
1,592 KB
testcase_29 AC 801 ms
1,588 KB
testcase_30 AC 837 ms
1,592 KB
testcase_31 AC 807 ms
1,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 DEBUG=0;

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);
  int seed=('k'<<16)^('i'<<15)^('r'<<14)^('i'<<13)^('k'<<12)^('a'<<11);
  mt19937 mt(seed);
  vector<pii> cur(ans);
  int sc=ma;
  bool fire=true;
  vector<vi> len(26);
  rep(i,k)len[l[i]].push_back(i);
  for(int u=25;u>=1;--u){
    if(len[u].size()==0)continue;
    rep(iter,(2<=u&&u<=6?50:20)){
      if(DEBUG){
	if(iter%200==0){
	  cerr<<"len="<<u<<" "<<iter<<":"<<sc<<endl;
	  fire=true;
	}
      }
      vector<pii> nxt(cur);
      int idx=len[u][mt()%len[u].size()];
      pair<int,pii> tt(-1,pii(-1,-1));
      rep(j,N){
	nxt[idx].first=mt()%(N-l[idx]+1)+1;
	nxt[idx].second=-(j+1);
	tt=max(tt,make_pair(calc_score(nxt),nxt[idx]));
      }
      rep(i,N){
	nxt[idx].first=i+1;
	nxt[idx].second=mt()%(N-l[idx]+1)+1;
	tt=max(tt,make_pair(calc_score(nxt),nxt[idx]));
      }
      nxt[idx]=tt.second;
      int nxtsc=calc_score(nxt);
      if(nxtsc>=sc){
	cur=nxt;
	sc=nxtsc;
      }
      if(sc>ma){
	if(DEBUG){
	  if(fire){
	    cerr<<"updmax "<<ma<<"->"<<sc<<endl;
	    fire=false;
	  }
	}
	ma=sc;
	ans=cur;
      }
    }
  }
  //output
  output(ans);
}
0