結果

問題 No.5002 stick xor
ユーザー kurenai3110kurenai3110
提出日時 2018-05-26 05:12:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 909 ms / 1,000 ms
コード長 6,938 bytes
コンパイル時間 32,864 ms
実行使用メモリ 1,724 KB
スコア 44,781
最終ジャッジ日時 2018-05-26 05:13:24
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 905 ms
1,720 KB
testcase_01 AC 904 ms
1,716 KB
testcase_02 AC 905 ms
1,720 KB
testcase_03 AC 905 ms
1,724 KB
testcase_04 AC 907 ms
1,720 KB
testcase_05 AC 907 ms
1,716 KB
testcase_06 AC 905 ms
1,720 KB
testcase_07 AC 908 ms
1,720 KB
testcase_08 AC 906 ms
1,720 KB
testcase_09 AC 908 ms
1,716 KB
testcase_10 AC 906 ms
1,720 KB
testcase_11 AC 904 ms
1,724 KB
testcase_12 AC 904 ms
1,720 KB
testcase_13 AC 907 ms
1,724 KB
testcase_14 AC 907 ms
1,720 KB
testcase_15 AC 905 ms
1,716 KB
testcase_16 AC 907 ms
1,720 KB
testcase_17 AC 908 ms
1,720 KB
testcase_18 AC 905 ms
1,720 KB
testcase_19 AC 907 ms
1,716 KB
testcase_20 AC 907 ms
1,716 KB
testcase_21 AC 907 ms
1,716 KB
testcase_22 AC 909 ms
1,724 KB
testcase_23 AC 908 ms
1,716 KB
testcase_24 AC 905 ms
1,720 KB
testcase_25 AC 906 ms
1,716 KB
testcase_26 AC 905 ms
1,716 KB
testcase_27 AC 908 ms
1,720 KB
testcase_28 AC 906 ms
1,716 KB
testcase_29 AC 908 ms
1,720 KB
testcase_30 AC 906 ms
1,720 KB
testcase_31 AC 908 ms
1,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize "O3"
#pragma GCC target "avx"
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <chrono>
#include <bitset>
#include <cmath>
using namespace std;

class Timer {
	chrono::high_resolution_clock::time_point start, end;
	double limit;

public:
	Timer() {
		start = chrono::high_resolution_clock::now();
	}
	Timer(double l) {
		start = chrono::high_resolution_clock::now();
		limit = l;
	}

	double getTime() {
		end = chrono::high_resolution_clock::now();
		return chrono::duration<double>(end - start).count();
	}

	bool Over() {
		if (getTime() > limit) {
			return true;
		}
		return false;
	}

	void setLimit(double l) {
		limit = l;
	}
	void setStart() { start = chrono::high_resolution_clock::now(); }
	double getLimit() { return limit; }
};
class Xor128 {
	unsigned static int x, y, z, w;
public:
	Xor128() {
		x = 31103110, y = 123456789, z = 521288629, w = 88675123;
	}

	unsigned int rand()
	{
		unsigned int t;
		t = (x ^ (x << 11)); x = y; y = z; z = w;
		return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
	}
};
unsigned int Xor128::x, Xor128::y, Xor128::z, Xor128::w;

const double TIMELIMIT = 0.9;

struct ANS {
	char mode;
	int r, c;

	ANS(char mode = -1, int r = 0, int c = 0):mode(mode), r(r), c(c) {}
};

class Solver{
	int N, K;
	int L[500];
	int A[60][60];
	int sumA0[61][61], sumA1[61][61];

	Timer tmr;
	Xor128 xor128;

	vector<ANS>ans, best_ans;
	int best_score;
public:

	void input() {
		cin >> N >> K;
		for (int i = 0; i < K; i++)cin >> L[i];
		for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) {
			char a; cin >> a; a -= '0';
			A[i][j] = a;
		}
	}

	void init() {
		input();

		tmr.setStart();

		for (int i = 0; i <= N; i++) {
			for (int j = 0; j <= N; j++) {
				sumA0[j][i] = sumA1[i][j] = 0;
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				sumA0[j][i + 1] += sumA0[j][i] + A[i][j];
				sumA1[i][j + 1] += sumA1[i][j] + A[i][j];
			}
		}

		ans.resize(K);

		best_score = 0;
		for (int i = 0; i < K; i++) {
			best_score += scoring(false, 0, 0, i);
			ans[i].mode = false;
			update(0, 0, 0, i);
		}

		best_ans = ans;

		tmr.setLimit(TIMELIMIT);
	}
	void SA() {
		double startTemp = 1, endTemp = 0.05;
		double diffTemp = (endTemp - startTemp) / TIMELIMIT;

		double current_time = tmr.getTime();

		int score = best_score;

		bool mode2 = false;

		int loop = 0;
		int i = 0;
		while (current_time < TIMELIMIT) {
			i = (i + 1) % K;

			loop++;
			if (loop % 10000 == 0) {
				current_time = tmr.getTime();
				if (current_time > TIMELIMIT*0.8)mode2 = true;
			}

			int tmp2 = 0;
			if (ans[i].mode != -1) {
				int r = ans[i].r;
				int c = ans[i].c;
				int mode = ans[i].mode;

				if (mode) tmp2 += (sumA1[r][c + L[i]] - sumA1[r][c]);
				else tmp2 += (sumA0[c][r + L[i]] - sumA0[c][r]);
			}
			tmp2 *= 2;
			tmp2 -= L[i];

			if (mode2 == false && L[i]>5) {
				if (tmp2 < -0.5*L[i])continue;
			}

			int change = -1e9;
			bool mode;
			int r, c;
			for (int t = 0; t < L[i] + 2; t++) {
				bool tmode = xor128.rand() % 2;
				int tr = xor128.rand() % (N - L[i] + 1);
				int tc = xor128.rand() % N;

				if (tmode)swap(tr, tc);

				if (t == 0) {
					tmode = ans[i].mode;
					tr = ans[i].r;
					tc = ans[i].c;

					if (tmode) {
						tc -= xor128.rand() % 3 + 1;
						if (tc < 0)continue;
					}
					else {
						tr -= xor128.rand() % 3 + 1;
						if (tr < 0)continue;
					}
				}
				else if (t == 1) {
					tmode = ans[i].mode;
					tr = ans[i].r;
					tc = ans[i].c;

					if (tmode) {
						tc += xor128.rand() % 3 + 1;
						if (tc >= (N - L[i] + 1))continue;
					}
					else {
						tr += xor128.rand() % 3 + 1;
						if (tr >= (N - L[i] + 1))continue;
					}
				}

				int tmp = scoring(tmode, tr, tc, i) + tmp2;

				if (t < 2) if (mode2 == false)continue;

				if (tmp >= change) {
					mode = tmode;
					r = tr;
					c = tc;
					change = tmp;
				}
			}


			bool accept = false;
			if (change >= 0)accept = true;
			else if (change < -2)accept = false;
			else {
				double temp = startTemp + diffTemp * tmr.getTime();
				double prob = exp(change / temp);
				accept = prob * UINT32_MAX > xor128.rand();
			}


			if (accept) {
				score += change;

				update(ans[i].mode, ans[i].r, ans[i].c, i);

				ans[i].mode = mode;
				ans[i].r = r;
				ans[i].c = c;

				update(mode, r, c, i);

				if (score > best_score) {
					//if(mode2)cerr << current_time << " " << best_score << endl;
					best_score = score;
					best_ans = ans;
				}
			}
		}

		cerr << tmr.getTime() << endl;
		cerr << loop << endl;
		cerr << best_score << endl;
	}

	int scoring(bool mode, int r, int c, int i) {
		int change = 0;

		int* sA;
		if (mode)sA = sumA1[r];
		else sA = sumA0[c];

		if (mode) change += (sA[c + L[i]] - sA[c]);
		else change += (sA[r + L[i]] - sA[r]);

		change -= L[i];

		int r1, r2;
		r1 = r; r2 = ans[i].r;
		int c1, c2;
		c1 = c; c2 = ans[i].c;


		if (mode == ans[i].mode) {
			if (mode == true && r1 == r2) {
				if (c1 > c2)swap(c1, c2);
				if (c1 + L[i] > c2)change += ((c1 + L[i] - c2) - 2 * (sA[c1 + L[i]] - sA[c2]));
			}
			if (mode == false && c1 == c2) {
				if (r1 > r2)swap(r1, r2);
				if (r1 + L[i] > r2)change += ((r1 + L[i] - r2) - 2 * (sA[r1 + L[i]] - sA[r2]));
			}
		}
		else if (ans[i].mode != -1) {
			if (mode) {
				if (c1 <= c2 && c2 <= c1 + L[i] - 1 && r2 <= r1 && r1 <= r2 + L[i] - 1) {
					change -= (A[r1][c2] ? 1 : -1);
				}
			}
			else {
				if (r1 <= r2 && r2 <= r1 + L[i] - 1 && c2 <= c1 && c1 <= c2 + L[i] - 1) {
					change -= (A[r2][c1] ? 1 : -1);
				}
			}
		}

		change *= 2;
		change += L[i];

		return change;
	}

	void update(bool mode, int r, int c, int i) {
		int rev_mode = mode ^ 1;
		if (mode) {
			int p = 0;
			for (int j = c; j < c + L[i]; j++) {
				if(mode)sumA1[r][j] += p;
				else sumA0[j][r] += p;

				int p2 = (A[r][j] ? -1 : 1);
				for (int k = r + 1; k <= N; k++) {
					if(rev_mode)sumA1[k][j] += p2;
					else sumA0[j][k] += p2;
				}

				p += (A[r][j] ? -1 : 1);
				A[r][j] ^= 1;
			}
			for (int j = c + L[i]; j <= N; j++) {
				if (mode)sumA1[r][j] += p;
				else sumA0[j][r] += p;
			}
		}
		else {
			int p = 0;
			for (int j = r; j < r + L[i]; j++) {
				if (mode)sumA1[j][c] += p;
				else sumA0[c][j] += p;

				int p2 = (A[j][c] ? -1 : 1);
				for (int k = c + 1; k <= N; k++) {
					if(rev_mode)sumA1[j][k] += p2;
					else sumA0[k][j] += p2;
				}

				p += (A[j][c] ? -1 : 1);
				A[j][c] ^= 1;
			}
			for (int j = r + L[i]; j <= N; j++) {
				if (mode)sumA1[j][c] += p;
				else sumA0[c][j] += p;
			}
		}
	}

	void output() {
		for (int i = 0; i < K; i++) {
			cout << best_ans[i].r + 1 << " " << best_ans[i].c + 1 << " ";

			if (best_ans[i].mode)cout << best_ans[i].r + 1 << " " << best_ans[i].c + L[i] << endl;
			else cout << best_ans[i].r + L[i] << " " << best_ans[i].c + 1 << endl;
		}
	}

	void run() {
		init();
		SA();
		output();
	}
};

int main() {
	Solver slv;
	slv.run();
	
	return 0;
}
0