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

• 問題: No.5002 stick xor
• ユーザー: gazelle
• 提出日時: 2018-05-31 02:12:06
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 969 ms / 1,000 ms
• コード長: 3,994 bytes
• コンパイル時間: 39,248 ms
• 実行使用メモリ: 1,592 KB
• スコア: 22,301
• 最終ジャッジ日時: 2018-05-31 02:12:50
• ジャッジサーバーID （参考情報）: judge6 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	956 ms; 1,588 KB
testcase_01	AC	964 ms; 1,588 KB
testcase_02	AC	964 ms; 1,588 KB
testcase_03	AC	965 ms; 1,588 KB
testcase_04	AC	956 ms; 1,592 KB
testcase_05	AC	955 ms; 1,588 KB
testcase_06	AC	955 ms; 1,588 KB
testcase_07	AC	958 ms; 1,588 KB
testcase_08	AC	960 ms; 1,592 KB
testcase_09	AC	960 ms; 1,592 KB
testcase_10	AC	955 ms; 1,588 KB
testcase_11	AC	956 ms; 1,588 KB
testcase_12	AC	956 ms; 1,588 KB
testcase_13	AC	958 ms; 1,592 KB
testcase_14	AC	957 ms; 1,588 KB
testcase_15	AC	961 ms; 1,592 KB
testcase_16	AC	963 ms; 1,588 KB
testcase_17	AC	954 ms; 1,588 KB
testcase_18	AC	954 ms; 1,588 KB
testcase_19	AC	959 ms; 1,592 KB
testcase_20	AC	957 ms; 1,588 KB
testcase_21	AC	958 ms; 1,592 KB
testcase_22	AC	969 ms; 1,592 KB
testcase_23	AC	958 ms; 1,588 KB
testcase_24	AC	954 ms; 1,588 KB
testcase_25	AC	955 ms; 1,584 KB
testcase_26	AC	962 ms; 1,592 KB
testcase_27	AC	953 ms; 1,588 KB
testcase_28	AC	956 ms; 1,588 KB
testcase_29	AC	959 ms; 1,592 KB
testcase_30	AC	956 ms; 1,588 KB
testcase_31	AC	957 ms; 1,592 KB

ソースコード

#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<random>
#include<time.h>
#define MOD 1000000007ll
#define INF 1000000000ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<(ll)m; i++)
#define FOR(i,n,m) for(long long i=n; i<(ll)m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

struct cell {
	int row;
	int col;
};
enum dir {
	HORIZONTAL=0,
	VERTICAL=1,
};

struct op {
	dir d;
	cell c;
};

int n,k;
int l[500];
int a[60][60];
op ret[500];

int rd() {
	static random_device rd;
	static mt19937 mt(rd());
	return abs((int)mt());
}

int counter(dir d, cell c, int lgt, bool flag) {
	if(c.row<0||c.row>=n||c.col<0||c.col>=n) return -INF;
	if(d==HORIZONTAL&&c.col+lgt>n) return -INF;
	if(d==VERTICAL&&c.row+lgt>n) return -INF;
	int ret=0;
	if(d==HORIZONTAL) REP(i,lgt) ret+=flag^!a[c.row][c.col+i];
	if(d==VERTICAL) REP(i,lgt) ret+=flag^!a[c.row+i][c.col];
	return ret;
}

void update(int updidx, op o, int lgt) {
	dir d=o.d;
	cell c=o.c;
	if(updidx==-1) {
		if(d==HORIZONTAL) REP(i,lgt) a[c.row][c.col+i]^=1;
		if(d==VERTICAL) REP(i,lgt) a[c.row+i][c.col]^=1;
	}
	switch(updidx) {
		case 0: { d=(d==HORIZONTAL ? VERTICAL : HORIZONTAL); break; }
		case 1: { c.row--; break; }
		case 2: { c.row++; break; }
		case 3: { c.col--; break; }
		case 4: { c.col++; break; }
		case -1: return;
	}
	if(d==HORIZONTAL) REP(i,lgt) a[c.row][c.col+i]^=1;
	if(d==VERTICAL) REP(i,lgt) a[c.row+i][c.col]^=1;
	return;
}

op newop(op o, int lgt) {
	dir d=o.d;
	cell c=o.c;
	int cnt=counter(d,c,lgt,0);
	update(-1,o,lgt);
	int maxupd=0,updidx=-1,buf=0;
	buf=counter((dir)!d,c,lgt,1)-cnt;
	if(buf>maxupd) { maxupd=buf; updidx=0; }
	buf=counter(d,{c.row-1,c.col},lgt,1)-cnt;
	if(buf>maxupd) { maxupd=buf; updidx=1; }
	buf=counter(d,{c.row+1,c.col},lgt,1)-cnt;
	if(buf>maxupd) { maxupd=buf; updidx=2; }
	buf=counter(d,{c.row,c.col-1},lgt,1)-cnt;
	if(buf>maxupd) { maxupd=buf; updidx=3; }
	buf=counter(d,{c.row,c.col+1},lgt,1)-cnt;
	if(buf>maxupd) { maxupd=buf; updidx=4; }
	update(updidx,o,lgt);
	switch(updidx) {
		case 0: return {(dir)!d,c};
		case 1: return {d,{c.row-1,c.col}};
		case 2: return {d,{c.row+1,c.col}};
		case 3: return {d,{c.row,c.col-1}};
		case 4: return {d,{c.row,c.col+1}};
		default: return o;
	}
}

void input() {
	cin>>n>>k;
	REP(i,k) cin>>l[i];
	REP(i,n) REP(j,n) {
		char c;
		cin>>c;
		a[i][j]=(int)(c-'0');
	}
}

void output(op o, int lgt) {
	o.c.row++;
	o.c.col++;
	if(o.d==HORIZONTAL) cout<<o.c.row<<" "<<o.c.col<<" "<<o.c.row<<" "<<o.c.col+lgt-1<<endl;
	else cout<<o.c.row<<" "<<o.c.col<<" "<<o.c.row+lgt-1<<" "<<o.c.col<<endl;
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	input();
	REP(i,k) {
		if(rd()%2) {
			ret[i].d=HORIZONTAL;
			ret[i].c={rd()%n,rd()%(n-l[i]+1)};
			REP(j,l[i]) a[ret[i].c.row][ret[i].c.col+j]^=1;
		} else {
			ret[i].d=VERTICAL;
			ret[i].c={rd()%(n-l[i]+1),rd()%n};
			REP(j,l[i]) a[ret[i].c.row+j][ret[i].c.col]^=1;
		}
	}
	/*/
	REP(i,k) output(ret[i],l[i]);
	REP(i,n) {
		REP(j,n) cout<<a[i][j];
		cout<<endl;
	}*/

	int hoge=0;
	clock_t strt=clock();
	clock_t crrt=clock();
	while(crrt-strt<950000) {
		int tgt=rd()%k;
		op buf=ret[tgt];
		ret[tgt]=newop(ret[tgt],l[tgt]);
		/*if(buf.d!=ret[tgt].d||buf.c.row!=ret[tgt].c.row||buf.c.col!=ret[tgt].c.col) {
			cout<<buf.d<<" "<<buf.c.row<<" "<<buf.c.col<<endl;
			cout<<ret[tgt].d<<" "<<ret[tgt].c.row<<" "<<ret[tgt].c.col<<endl;
			hoge++;
		}*/
		crrt=clock();
	}
	REP(i,k) output(ret[i],l[i]);
	/*
	REP(i,n) {
 		REP(j,n) cout<<a[i][j];
		cout<<endl;
	}
	cout<<hoge<<endl;
	 */
}