結果

問題 No.5002 stick xor
ユーザー gazellegazelle
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
	 */
}
0