結果

問題 No.5002 stick xor
ユーザー ats5515ats5515
提出日時 2018-06-01 21:33:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 989 ms / 1,000 ms
コード長 10,594 bytes
コンパイル時間 34,627 ms
実行使用メモリ 2,152 KB
スコア 52,625
最終ジャッジ日時 2018-06-01 21:33:50
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

// C++11
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <assert.h>
#include <fstream>
#include <iomanip>

using namespace std;

const int64_t CYCLES_PER_SEC = 2600000000;
const int N = 60;
const int K = 500;
struct Timer {
	int64_t start;
	Timer() { reset(); }
	void reset() { start = getCycle(); }
	void plus(double a) { start -= (a * CYCLES_PER_SEC); }
	inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
	inline int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}
};
class XorShift {
public:
	unsigned int x, y, z, w;
	double nL[65536];

	XorShift()
	{
		init();
	}

	void init()
	{
		x = 314159265; y = 358979323; z = 846264338; w = 327950288;
		double n = 1 / (double)(2 * 65536);
		for (int i = 0; i < 65536; i++) {
			nL[i] = log(((double)i / 65536) + n);
		}
	}
	void seeding(int seed) {
		x = 314159265; y = 358979323; z = 846264338; w = ((long long)327950288 * (seed + 1)) % 1000000007;
		for (int i = 0; i < 1000 + (seed % 1000); i++) {
			next();
		}
	}
	inline unsigned int next()
	{
		unsigned int t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
	}

	inline double nextLog() {
		return nL[next() & 0xFFFF];
	}

	inline int nextInt(int m)
	{
		return (int)(next() % m);
	}


	int nextInt(int min, int max)
	{
		return min + nextInt(max - min + 1);
	}


	inline double nextDouble()
	{
		return (double)next() / ((long long)1 << 32);
	}


};
//The board is rotated by 90 degrees
enum Orientation {
	VERTICAL,
	HORIZONTAL
};
struct Rectangle {
	int leftX;
	int topY;
	Orientation o;
};

typedef char Grid_t;
struct State {
	Rectangle rects[K];
	Grid_t grid[N][N];
	void init(Grid_t _grid[N][N]) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				grid[i][j] = _grid[i][j];
			}
		}
	}
	int calcScore() {
		int res = N * N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				res -= grid[i][j];
			}
		}
		return res;
	}
	int doPlace(int i, int L) {
		int res = 0;
		if (rects[i].o == VERTICAL) {
			int x = rects[i].leftX;
			for (int y = rects[i].topY; y < rects[i].topY + L; y++) {
				res += grid[x][y];
				grid[x][y] = 1 - grid[x][y];
			}
		}
		else {
			int y = rects[i].topY;
			for (int x = rects[i].leftX; x < rects[i].leftX + L; x++) {
				res += grid[x][y];
				grid[x][y] = 1 - grid[x][y];
			}
		}
		return res * 2 - L;
	}
	int erase(int i, int L) {
		int res = 0;
		if (rects[i].o == VERTICAL) {
			int x = rects[i].leftX;
			for (int y = rects[i].topY; y < rects[i].topY + L; y++) {
				res += grid[x][y];
				grid[x][y] = 1 - grid[x][y];
			}
		}
		else {
			int y = rects[i].topY;
			for (int x = rects[i].leftX; x < rects[i].leftX + L; x++) {
				res += grid[x][y];
				grid[x][y] = 1 - grid[x][y];
			}
		}
		return res * 2 - L;
	}

	int placeGreedy(int i, int L, XorShift &rnd) {
		int ones;
		int mx = -1;
		int rr = -1;
		int l;
		int sc;
		//if (rects[i].o == VERTICAL) {
		for (int x = 0; x < N; x++) {
			ones = 0;
			for (int y = 0; y < L; y++) {
				ones += grid[x][y];
			}
			l = 0;
			while (true) {
				if (rr <= ones) {
					sc = (ones << 12) + (rnd.next() & 0xFFF);
					if (mx < sc) {
						rr = ones;
						mx = sc;
						rects[i].leftX = x;
						rects[i].topY = l;
						rects[i].o = VERTICAL;
					}
				}
				if (l + L >= N)break;
				ones += grid[x][l + L];
				ones -= grid[x][l];
				l++;
			}
		}
		/*	}
			else {*/

		for (int y = 0; y < N; y++) {
			ones = 0;
			for (int x = 0; x < L; x++) {
				ones += grid[x][y];
			}
			l = 0;
			while (true) {
				if (rr <= ones) {
					sc = (ones << 12) + (rnd.next() & 0xFFF);
					if (mx < sc) {
						mx = sc;
						rr = ones;
						rects[i].leftX = l;
						rects[i].topY = y;
						rects[i].o = HORIZONTAL;
					}
				}
				if (l + L >= N)break;
				ones += grid[l + L][y];
				ones -= grid[l][y];
				l++;
			}
		}

		//}
		return doPlace(i, L);
	}
	
};
class Solver {
public:
	XorShift rnd;
	Timer timer;

	//////TASK///////
	Grid_t grid[N][N];
	int L[K];
	int L_sorted[K];
	int h[27];
	int W0;
	/////////////////

	State state;
	void inputFromStdin() {
		int _;
		cin >> _ >> _;
		for (int i = 0; i < K; i++) {
			cin >> L[i];
		}
		W0 = N * N;
		char a;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> a;
				grid[i][j] = a - '0';
				W0 -= grid[i][j];
			}
		}
	}
	void generateTestCase(int seed) {
		XorShift gen;
		gen.seeding(seed);
		for (int i = 0; i < K; i++) {
			L[i] = gen.nextInt(25) + 1;
		}
		sort(L, L + K, greater<int>());
		W0 = N * N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				grid[i][j] = gen.nextInt(2);
				W0 -= grid[i][j];
			}
		}
		ofstream ofs("input.txt");
		ofs << N << " " << K << endl;
		for (int i = 0; i < K; i++) {
			if (i > 0)ofs << " ";
			ofs << L[i];
		}
		ofs << endl;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ofs << (int)grid[i][j];
			}
			ofs << endl;
		}
	}
	void outputResult() {
		int head[25];
		for (int i = 0; i < K; i++) {
			if (i == 0 || L_sorted[i] > L_sorted[i - 1]) {
				head[L_sorted[i] - 1] = i;
			}
		}
		for (int i = 0; i < K; i++) {
			Rectangle &r = state.rects[head[L[i] - 1]];
			if (r.o == VERTICAL) {
				cout << r.leftX + 1 << " " << r.topY + 1 << " " << r.leftX + 1 << " " << r.topY + L[i] << endl;
			}
			else {
				cout << r.leftX + 1 << " " << r.topY + 1 << " " << r.leftX + L[i] << " " << r.topY + 1 << endl;
			}
			head[L[i] - 1]++;
		}
	}
	void outputDebugInfo() {
		int W1 = state.calcScore();
		cerr << "W0 = " << W0 << ", W1 = " << W1 << endl;
		cerr << "score = " << W1 - W0 << endl;
	}
	int getScore() {
		int W1 = state.calcScore();
		return W1 - W0;
	}
	void init() {

		state.init(grid);
		for (int i = 0; i < K; i++) {
			L_sorted[i] = L[i];
		}
		sort(L_sorted, L_sorted + K);
		h[0] = 0;
		for (int i = 0; i < K; i++) {
			if (i == 0 || L_sorted[i] > L_sorted[i - 1]) {
				h[L_sorted[i]] = i;
			}
		}
		h[26] = K;
	}
	void SA(double timelimit) {
		int score = state.calcScore();
		/*for (int i = K - 1; i >= 0; i--) {
			score += state.placeGreedy(i, L_sorted[i], rnd);
		}*/
		/*for (int i = 0; i < K; i++) {
		score += state.placeGreedy(i, L_sorted[i], rnd);
		}*/
		double ti;
		int a;
		int o;
		int cnt = 0;
		cerr << score << endl;
		cerr << state.calcScore() << endl;

		a = K - 1;
		double st = timer.get();
		cerr << "st=" << st << endl;
		double di = st;
		double dd = (timelimit - st) * 0.1;
		double rem;
		Rectangle tmp;
		double T;
		double T0 = 0.8;
		int bscore;
		int br = 500;
		int rr;
		int mnL = K;

		int xa;
		int ya;
		int xb;
		int yb;
		int la;
		int b;
		int lb;
		Rectangle ba, bb;
		while (true) {
			if ((cnt & 0x3FF) == 0) {
				ti = timer.get();
				if (ti > timelimit) {
					break;
				}
				rem = (timelimit - ti) / (timelimit - st);
				if (rem > 0) {
					//rr = 350 * rem;
					rr = 350 * rem*rem;
					if (rr < br) {
						for (int i = br - 1; i >= rr; i--) {
							score += state.placeGreedy(i, L_sorted[i], rnd);
						}
						br = rr;
						mnL = min(mnL, rr);
					}
				}

				T = T0 * rem;
				if (di < ti) {
					di += dd;
					cerr << score << "  " << rr << endl;
				}
			}
			cnt++;
			bscore = score;
			if (rnd.nextDouble() < 0.0015) {
				a = rnd.nextInt(rr, K - 1);
				score += state.erase(a, L_sorted[a]);
				score += state.placeGreedy(a, L_sorted[a], rnd);
			}
			else {
				
				a = rnd.nextInt(rr, h[25] - 1);
				la = L_sorted[a];
				ba = state.rects[a];
				if (state.rects[a].o == VERTICAL) {
					if (cnt & 1) {
						if (state.rects[a].topY > 0) {
							score += 2 * state.grid[state.rects[a].leftX][state.rects[a].topY - 1] - 1;
							state.rects[a].topY--;
							xa = state.rects[a].leftX;
							ya = state.rects[a].topY;
							state.grid[xa][ya] ^= 1;
						}
						else {
							continue;
						}
					}
					else {
						if (state.rects[a].topY + la < N) {
							score += 2 * state.grid[state.rects[a].leftX][state.rects[a].topY + la] - 1;
							xa = state.rects[a].leftX;
							ya = state.rects[a].topY + la;
							state.grid[xa][ya] ^= 1;
						}
						else {
							continue;
						}
					}
				}
				else {
					if (cnt & 1) {
						if (state.rects[a].leftX > 0) {
							score += 2 * state.grid[state.rects[a].leftX - 1][state.rects[a].topY] - 1;
							state.rects[a].leftX--;
							xa = state.rects[a].leftX;
							ya = state.rects[a].topY;
							state.grid[xa][ya] ^= 1;
						}
						else {
							continue;
						}
					}
					else {
						if (state.rects[a].leftX + la < N) {
							score += 2 * state.grid[state.rects[a].leftX + la][state.rects[a].topY] - 1;
							xa = state.rects[a].leftX + la;
							ya = state.rects[a].topY;
							state.grid[xa][ya] ^= 1;
						}
						else {
							continue;
						}
					}
				}
				b = rnd.nextInt(h[la + 1], h[la + 2] - 1);
				bb = state.rects[b];
				lb = L_sorted[b];
				//if (lb != la + 1)assert(false);
				if (state.rects[b].o == VERTICAL) {
					if (cnt & 1) {
						score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY] - 1;
						xb = state.rects[b].leftX;
						yb = state.rects[b].topY;
						state.rects[b].topY++;
					}
					else {
						score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY + lb - 1] - 1;
						xb = state.rects[b].leftX;
						yb = state.rects[b].topY + lb - 1;
					}
				}
				else {
					if (cnt & 1) {
						score += 2 * state.grid[state.rects[b].leftX][state.rects[b].topY] - 1;
						xb = state.rects[b].leftX;
						yb = state.rects[b].topY;
						state.rects[b].leftX++;
					}
					else {
						score += 2 * state.grid[state.rects[b].leftX + lb - 1][state.rects[b].topY] - 1;
						xb = state.rects[b].leftX + lb - 1;
						yb = state.rects[b].topY;
					}
				}
				if (score - bscore > T*rnd.nextLog()) {
					swap(state.rects[a], state.rects[b]);
					state.grid[xb][yb] ^= 1;
					//cerr << "ok" << endl;
				}
				else {
					score = bscore;
					state.rects[a] = ba;
					state.rects[b] = bb;
					state.grid[xa][ya] ^= 1;
				}
			}
		}
		cerr << score << endl;
		cerr << "cnt = " << cnt << endl;
	}

	void solve() {
		init();
		SA(0.98);
		outputDebugInfo();
	}
};

//#define Batch
#ifdef Batch
int main() {
	ofstream ofs("result.csv");
	for (int seed = 0; seed < 30; seed++) {
		Solver solver;
		solver.generateTestCase(seed);
		solver.solve();
		ofs << seed << "," << solver.getScore() << endl;
	}
}
#else
int main() {
	Solver solver;
	//solver.generateTestCase(10);
	solver.inputFromStdin();
	solver.solve();
	solver.outputResult();
}
#endif // Batch
0