結果

問題 No.5002 stick xor
ユーザー kurenai3110kurenai3110
提出日時 2018-05-26 02:18:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 905 ms / 1,000 ms
コード長 6,723 bytes
コンパイル時間 31,598 ms
実行使用メモリ 1,704 KB
スコア 43,881
最終ジャッジ日時 2018-05-26 02:19:01
ジャッジサーバーID
（参考情報） 		judge10 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <chrono>
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;

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

	Timer tmr;
	Xor128 xor128;

	vector<pair<char, pair<int, int>>>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++) {
			cin >> A[i][j];
			A[i][j] -= '0';
		}
	}

	void init() {
		input();

		tmr.setStart();

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

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

		ans.resize(K, make_pair(-1, make_pair(0, 0)));

		best_score = 0;
		for (int i = 0; i < K; i++) {
			best_score += scoring(0, 0, 0, i);
			ans[i].first = 0;
			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;

		int loop = 0;
		int i = 0;
		while (current_time < TIMELIMIT) {
			loop++;
			if (loop % 1000 == 0) {
				current_time = tmr.getTime();
			}

			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].first;
					tr = ans[i].second.first;
					tc = ans[i].second.second;

					if (tmode) {
						tc -= 1;
						if (tc < 0)continue;
					}
					else {
						tr -= 1;
						if (tr < 0)continue;
					}
				}
				else if (t == 1) {
					tmode = ans[i].first;
					tr = ans[i].second.first;
					tc = ans[i].second.second;

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

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

				if (t < 2) if(current_time < TIMELIMIT*0.8)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].first, ans[i].second.first, ans[i].second.second, i);

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

				update(mode, r, c, i);

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

			}

			i = (i + 1) % K;
		}

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

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

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

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

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

		change -= L[i];

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


		if (mode == ans[i].first) {
			if (mode == true && r1 == r2) {
				if (c1 > c2)swap(c1, c2);
				if (c1 + L[i] > c2)change += ((c1 + L[i] - c2) - 2 * (sumA1[r][c1 + L[i]] - sumA1[r][c2]));
			}
			if (mode == false && c1 == c2) {
				if (r1 > r2)swap(r1, r2);
				if (r1 + L[i] > r2)change += ((r1 + L[i] - r2) - 2 * (sumA0[r1 + L[i]][c] - sumA0[r2][c]));
			}
		}
		else if (ans[i].first != -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;
		if (ans[i].first == -1)change += L[i];

		return change;
	}

	void update(int 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[r][j] += 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[k][j] += 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[r][j] += p;
			}
		}
		else {
			int p = 0;
			for (int j = r; j < r + L[i]; j++) {
				if (mode)sumA1[j][c] += p;
				else sumA0[j][c] += 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[j][k] += 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[j][c] += p;
			}
		}
	}

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

			if (best_ans[i].first)cout << best_ans[i].second.first + 1 << " " << best_ans[i].second.second + L[i] << endl;
			else cout << best_ans[i].second.first + L[i] << " " << best_ans[i].second.second + 1 << endl;
		}
	}

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

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