結果

問題 No.5002 stick xor
ユーザー kurenai3110kurenai3110
提出日時 2018-05-27 08:13:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 958 ms / 1,000 ms
コード長 9,391 bytes
コンパイル時間 35,084 ms
実行使用メモリ 1,796 KB
スコア 48,429
最終ジャッジ日時 2018-05-27 08:14:32
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 957 ms
1,792 KB
testcase_01 AC 956 ms
1,788 KB
testcase_02 AC 956 ms
1,792 KB
testcase_03 AC 956 ms
1,792 KB
testcase_04 AC 956 ms
1,788 KB
testcase_05 AC 955 ms
1,792 KB
testcase_06 AC 956 ms
1,792 KB
testcase_07 AC 958 ms
1,796 KB
testcase_08 AC 957 ms
1,788 KB
testcase_09 AC 958 ms
1,792 KB
testcase_10 AC 957 ms
1,788 KB
testcase_11 AC 957 ms
1,788 KB
testcase_12 AC 956 ms
1,788 KB
testcase_13 AC 957 ms
1,792 KB
testcase_14 AC 958 ms
1,788 KB
testcase_15 AC 955 ms
1,792 KB
testcase_16 AC 957 ms
1,788 KB
testcase_17 AC 956 ms
1,792 KB
testcase_18 AC 955 ms
1,788 KB
testcase_19 AC 956 ms
1,792 KB
testcase_20 AC 955 ms
1,792 KB
testcase_21 AC 957 ms
1,792 KB
testcase_22 AC 956 ms
1,788 KB
testcase_23 AC 958 ms
1,788 KB
testcase_24 AC 956 ms
1,792 KB
testcase_25 AC 956 ms
1,788 KB
testcase_26 AC 957 ms
1,792 KB
testcase_27 AC 955 ms
1,792 KB
testcase_28 AC 957 ms
1,788 KB
testcase_29 AC 956 ms
1,788 KB
testcase_30 AC 957 ms
1,792 KB
testcase_31 AC 955 ms
1,792 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;

const int TIME = 1;
const bool OUTPUT = true;
const double TIMELIMIT = 0.95;

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;

struct Point {
	int r, c;
	Point(int r = 0, int c = 0) :r(r), c(c) {}
};

struct ANS {
	char mode;
	Point p;

	ANS(char mode = -1, Point p = Point()):mode(mode), p(p) {}
};

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;

	Point kouho[3600];
	int k_size;
	int k_ind[60][60];


	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());

		k_size = 0;
		for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) {
			k_ind[i][j] = -1;
			if (A[i][j]) {
				k_ind[i][j] = k_size;
				kouho[k_size++] = Point(i, j);
			}
		}

		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, loop2 = 0;
		int i = 0;
		while (current_time < TIMELIMIT) {
			if (k_size == 0)break;

			i = (i + 1) % K;

			loop++; loop2++;
			if (loop2 == 10000) {
				current_time = tmr.getTime();
				if (mode2 == false && 6.*TIMELIMIT > 20.*(TIMELIMIT - current_time)) {
					mode2 = true;
				}
				loop2 = 0;
			}

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

			int tmp2 = 0;
			if (ans[i].mode != -1) {
				int r = ans[i].p.r;
				int c = ans[i].p.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, tc;
				Point p = kouho[xor128.rand() % k_size];
				tr = p.r;
				tc = p.c;
				if(t>1)if ((tmode == true && tc >= N - L[i] + 1) || (tmode == false && tr >= N - L[i] + 1)) {
					t--;
					break;
				}

				if (t == 0) {
					tmode = ans[i].mode;
					tr = ans[i].p.r;
					tc = ans[i].p.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].p.r;
					tc = ans[i].p.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].p.r, ans[i].p.c, i);

				ans[i].mode = mode;
				ans[i].p.r = r;
				ans[i].p.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].p.r;
		int c1, c2;
		c1 = c; c2 = ans[i].p.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);
					if (A[r][j]) {
						int ind = k_ind[r][j];
						swap(kouho[ind], kouho[--k_size]);
						k_ind[kouho[ind].r][kouho[ind].c] = ind;
						k_ind[r][j] = -1;
					}
					else {
						k_ind[r][j] = k_size;
						kouho[k_size++] = Point(r, j);
					}
					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);
					if (A[r][j]) {
						int ind = k_ind[r][j];
						swap(kouho[ind], kouho[--k_size]);
						k_ind[kouho[ind].r][kouho[ind].c] = ind;
						k_ind[r][j] = -1;
					}
					else {
						k_ind[r][j] = k_size;
						kouho[k_size++] = Point(r, j);
					}
					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);
					if (A[j][c]) {
						int ind = k_ind[j][c];
						swap(kouho[ind], kouho[--k_size]);
						k_ind[kouho[ind].r][kouho[ind].c] = ind;
						k_ind[j][c] = -1;
					}
					else {
						k_ind[j][c] = k_size;
						kouho[k_size++] = Point(j, c);
					}
					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);
					if (A[j][c]) {
						int ind = k_ind[j][c];
						swap(kouho[ind], kouho[--k_size]);
						k_ind[kouho[ind].r][kouho[ind].c] = ind;
						k_ind[j][c] = -1;
					}
					else {
						k_ind[j][c] = k_size;
						kouho[k_size++] = Point(j, c);
					}
					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].p.r + 1 << " " << best_ans[i].p.c + 1 << " ";

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

	int run() {
		init();
		SA();
		if(OUTPUT)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;
}
0