#260671 (C++11) No.5002 stick xor

提出ソース

結果

問題	No.5002 stick xor
ユーザー	kurenai3110
提出日時	2018-05-26 20:51:46
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	960 ms / 1,000 ms
コード長	7,850 bytes
コンパイル時間	35,168 ms
実行使用メモリ	1,752 KB
スコア	47,381
最終ジャッジ日時	2018-05-26 20:52:22
ジャッジサーバーID （参考情報）	judge7 /
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	958 ms 1,748 KB
testcase_01	AC	955 ms 1,752 KB
testcase_02	AC	957 ms 1,752 KB
testcase_03	AC	956 ms 1,748 KB
testcase_04	AC	956 ms 1,748 KB
testcase_05	AC	955 ms 1,740 KB
testcase_06	AC	955 ms 1,748 KB
testcase_07	AC	957 ms 1,744 KB
testcase_08	AC	960 ms 1,752 KB
testcase_09	AC	956 ms 1,752 KB
testcase_10	AC	955 ms 1,748 KB
testcase_11	AC	957 ms 1,752 KB
testcase_12	AC	956 ms 1,748 KB
testcase_13	AC	958 ms 1,748 KB
testcase_14	AC	957 ms 1,748 KB
testcase_15	AC	958 ms 1,744 KB
testcase_16	AC	957 ms 1,748 KB
testcase_17	AC	956 ms 1,748 KB
testcase_18	AC	956 ms 1,748 KB
testcase_19	AC	957 ms 1,748 KB
testcase_20	AC	956 ms 1,744 KB
testcase_21	AC	954 ms 1,740 KB
testcase_22	AC	956 ms 1,748 KB
testcase_23	AC	958 ms 1,748 KB
testcase_24	AC	955 ms 1,748 KB
testcase_25	AC	957 ms 1,748 KB
testcase_26	AC	957 ms 1,744 KB
testcase_27	AC	957 ms 1,744 KB
testcase_28	AC	956 ms 1,748 KB
testcase_29	AC	958 ms 1,740 KB
testcase_30	AC	958 ms 1,748 KB
testcase_31	AC	957 ms 1,748 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;

const int TIME = 1;

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.95;

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 oA[60][60];
	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';
			oA[i][j] = a;
		}
	}

	void init() {
		tmr.setStart();

		for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)A[i][j] = oA[i][j];

		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.assign(K, ANS());

		best_score = 0;

		tmr.setLimit(TIMELIMIT);
	}

	void SA() {
		double startTemp = 1.6, endTemp = 0.02;
		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 (mode2 == false && 6.*TIMELIMIT > 20.*(TIMELIMIT - current_time)) {
					mode2 = true;
				}
			}

			if (L[i] * TIMELIMIT < 20.*(TIMELIMIT - current_time))continue;

			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] > 4) {
				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() % 4 + 1;
						if (tc < 0)continue;
					}
					else {
						tr -= xor128.rand() % 4 + 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() % 4 + 1;
						if (tc >= (N - L[i] + 1))continue;
					}
					else {
						tr += xor128.rand() % 4 + 1;
						if (tr >= (N - L[i] + 1))continue;
					}
				}

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

				if (t < 2) if (mode2 == false && UINT32_MAX *0.45 > xor128.rand() )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;

				if(ans[i].mode!=-1)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) {
					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) {
		if (mode) {
			int p = 0;
			if (N - c - L[i] + 1 < c) {
				for (int j = c; j < c + L[i]; j++) {
					sumA1[r][j] += p;

					int p2 = (A[r][j] ? -1 : 1);
					if (2 * r < N) for (int k = r; k >= 0; k--)sumA0[j][k] -= p2;
					else for (int k = r + 1; k <= N; k++)sumA0[j][k] += p2;

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

					p += (A[r][j] ? -1 : 1);
					A[r][j] ^= 1;

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

					int p2 = (A[j][c] ? -1 : 1);
					if (2 * r < N) for (int k = c; k >= 0; k--)sumA1[j][k] -= p2;
					else for (int k = c + 1; k <= N; k++)sumA1[j][k] += p2;			

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

					p += (A[j][c] ? -1 : 1);
					A[j][c] ^= 1;

					sumA0[c][j] -= p;
				}
				if (p)for (int j = r - 1; j >= 0; j--) 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;
		}
	}

	int run() {
		init();
		SA();
		output();
		return best_score;
	}
};

int main() {
	Solver slv;
	slv.input();
	double ave_score = 0;
	for (int t = 0; t < TIME; t++) {
		ave_score += slv.run();
	}
	cerr << 1. * ave_score / TIME << endl;
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード