結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 956 ms
2,148 KB
testcase_01 AC 957 ms
2,144 KB
testcase_02 AC 957 ms
2,144 KB
testcase_03 AC 957 ms
2,144 KB
testcase_04 AC 957 ms
2,144 KB
testcase_05 AC 957 ms
2,148 KB
testcase_06 AC 957 ms
2,144 KB
testcase_07 AC 956 ms
2,148 KB
testcase_08 AC 957 ms
2,144 KB
testcase_09 AC 957 ms
2,152 KB
testcase_10 AC 957 ms
2,152 KB
testcase_11 AC 957 ms
2,148 KB
testcase_12 AC 958 ms
2,148 KB
testcase_13 AC 957 ms
2,148 KB
testcase_14 AC 957 ms
2,144 KB
testcase_15 AC 959 ms
2,144 KB
testcase_16 AC 958 ms
2,148 KB
testcase_17 AC 957 ms
2,148 KB
testcase_18 AC 957 ms
2,148 KB
testcase_19 AC 957 ms
2,148 KB
testcase_20 AC 957 ms
2,148 KB
testcase_21 AC 956 ms
2,148 KB
testcase_22 AC 957 ms
2,152 KB
testcase_23 AC 957 ms
2,148 KB
testcase_24 AC 957 ms
2,144 KB
testcase_25 AC 957 ms
2,148 KB
testcase_26 AC 955 ms
2,152 KB
testcase_27 AC 957 ms
2,148 KB
testcase_28 AC 957 ms
2,152 KB
testcase_29 AC 958 ms
2,144 KB
testcase_30 AC 956 ms
2,152 KB
testcase_31 AC 957 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;
};
struct Range {
	int l, r, u, d;
};
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, Range &ra) {
		int ones;
		int mx = -1;
		int l;
		int sc;
		//if (rects[i].o == VERTICAL) {
		for (int x = ra.l; x < ra.r; x++) {
			ones = 0;
			for (int y = ra.u; y < ra.u + L; y++) {
				ones += grid[x][y];
			}
			l = ra.u;
			while (true) {
				sc = (ones << 12) + (rnd.next() & 0xFFF);
				if (mx < sc) {
					mx = sc;
					rects[i].leftX = x;
					rects[i].topY = l;
					rects[i].o = VERTICAL;
				}
				if (l + L >= ra.d)break;
				ones += grid[x][l + L];
				ones -= grid[x][l];
				l++;
			}
		}
		/*	}
		else {*/
		for (int y = ra.u; y < ra.d; y++) {
			ones = 0;
			for (int x = ra.l; x < ra.l + L; x++) {
				ones += grid[x][y];
			}
			l = ra.l;
			while (true) {
				sc = (ones << 12) + (rnd.next() & 0xFFF);
				if (mx < sc) {
					mx = sc;
					rects[i].leftX = l;
					rects[i].topY = y;
					rects[i].o = HORIZONTAL;
				}
				if (l + L >= ra.r)break;
				ones += grid[l + L][y];
				ones -= grid[l][y];
				l++;
			}
		}
		//}
		return doPlace(i, 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);
	}
	int placeGreedyH(int i, int L, XorShift &rnd) {
		int ones;
		int mx = -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) {
				sc = (ones << 12) + (rnd.next() & 0xFFF);
				if (mx < sc) {
					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) {
					sc = (ones << 12) + (rnd.next() & 0xFFF);
					if (mx < sc) {
						mx = sc;
						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);
	}
	int placeGreedyRange(int i, int L, XorShift &rnd, double range) {
		int ones;
		double mx = -1;
		int l;
		double sc;
		int res;
		for (int x = 0; x < N; x++) {
			ones = 0;
			for (int y = 0; y < L; y++) {
				ones += grid[x][y];
			}
			l = 0;
			while (true) {
				sc = ones + range * rnd.nextDouble();
				if (mx < sc) {
					mx = sc;
					res = ones;
					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++;
			}
		}
		for (int y = 0; y < N; y++) {
			ones = 0;
			for (int x = 0; x < L; x++) {
				ones += grid[x][y];
			}
			l = 0;
			while (true) {
				sc = ones + range * rnd.nextDouble();
				if (mx < sc) {
					mx = sc;
					res = 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++;
			}
		}
		doPlace(i, L);
		return res * 2 - 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 = 1.1;
		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;
					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.002) {
				a = rnd.nextInt(rr, K - 1);
				score += state.erase(a, L_sorted[a]);
				score += state.placeGreedy(a, L_sorted[a], rnd);
				/*tmp = state.rects[a];
				o = rnd.nextInt(2);
				if (o == 0) {
					state.rects[a].o = VERTICAL;
					state.rects[a].leftX = rnd.nextInt(N);
					state.rects[a].topY = rnd.nextInt(N + 1 - L_sorted[a]);
				}
				else {
					state.rects[a].o = HORIZONTAL;
					state.rects[a].leftX = rnd.nextInt(N + 1 - L_sorted[a]);
					state.rects[a].topY = rnd.nextInt(N);
				}
				score += state.doPlace(a, L_sorted[a]);
				if (score - bscore > T*rnd.nextLog()) {

				}
				else {
					score += state.erase(a, L_sorted[a]);
					state.rects[a] = tmp;
					score += state.doPlace(a, L_sorted[a]);
				}*/
			}
			else {
				
				a = rnd.nextInt(rr, h[25] - 1);
				la = L_sorted[a];
				ba = state.rects[a];
				if (state.rects[a].o == VERTICAL) {
					if (rnd.nextInt(2)) {
						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 (rnd.nextInt(2)) {
						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 (rnd.nextInt(2)) {
						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 (rnd.nextInt(2)) {
						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 greedy(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);
			}*/
		for (int i = 0; i < K; i++) {
			if (i % 2 == 0) {
				state.rects[i].o = VERTICAL;
			}
			else {
				state.rects[i].o = HORIZONTAL;
			}
		}
		double ti;
		int a;
		int cnt = 0;
		cerr << score << endl;
		cerr << state.calcScore() << endl;

		a = K - 1;
		double st = timer.get();
		double di = st;
		cerr << "st=" << st << endl;
		double dd = (timelimit - st)*0.1;
		double rem;
		int br = 500;
		int rr;
		int mnL = K;
		double m = 1.0 * timelimit;
		while (true) {
			ti = timer.get();
			if (ti > timelimit) {
				break;
			}
			rem = (m - ti) / (m - st);
			if (rem > 0) {
				rr = 450 * pow(rem, 3);
				if (rr < br) {
					for (int i = br - 1; i >= rr; i--) {
						score += state.placeGreedy(i, L_sorted[i], rnd);
					}
					br = rr;
					mnL = min(mnL, L_sorted[rr]);
				}
			}

			if (di < ti) {
				di += dd;
				cerr << score << " " << rr << endl;
			}
			cnt++;
			//if (rnd.nextDouble() < 0.5) {
			a = rnd.nextInt(rr, K - 1);
			//a = rnd.nextInt(rr, rr + 150);
			//if ((--a) == -1)a = -1;
			score += state.erase(a, L_sorted[a]);
			score += state.placeGreedy(a, L_sorted[a], rnd);
			/*}
			else {
				if (cnt & 1) {

				}
				else {

				}
			}*/
		}
		cerr << score << endl;
		cerr << "cnt = " << cnt << endl;
	}
	void greedy2(double timelimit) {
		vector<Range> ra(K);
		{
			/*int xx = 4;
			for (int i = 0; i < K; i++) {
				int ii = i % (xx*xx);
				int ll = L_sorted[i] + 15;
				ra[i].l = (ii % xx) * (N - ll) / (xx - 1);
				ra[i].u = (ii / xx) * (N - ll) / (xx - 1);
				ra[i].r = ra[i].l + ll;
				ra[i].d = ra[i].u + ll;
			}*/
			int xx = 4;
			for (int i = 0; i < K; i++) {
				int ii = i % (xx*xx);
				int ll = max(18, 2 * L_sorted[i] + 10);
				ra[i].l = (ii % xx) * (N - ll) / (xx - 1);
				ra[i].u = (ii / xx) * (N - ll) / (xx - 1);
				ra[i].r = ra[i].l + ll;
				ra[i].d = ra[i].u + ll;
			}
			/*for (int i = 0; i < K; i++) {

				ra[i].l = 0;
				ra[i].u = 0;
				ra[i].r = ra[i].l + 45;
				ra[i].d = ra[i].u + 45;
			}*/
		}
		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);
		}*/
		for (int i = 0; i < K; i++) {
			if (i % 2 == 0) {
				state.rects[i].o = VERTICAL;
			}
			else {
				state.rects[i].o = HORIZONTAL;
			}
		}
		double ti;
		int a;
		int cnt = 0;
		cerr << score << endl;
		cerr << state.calcScore() << endl;
		double di;
		a = K - 1;
		double st = timer.get();
		cerr << "st=" << st << endl;
		double dd = (timelimit - st)*0.1;
		double rem;
		int br = 500;
		int rr;
		while (true) {
			ti = timer.get();
			if (ti > timelimit) {
				break;
			}
			rem = (timelimit - ti) / (timelimit - st);
			rr = 350 * rem;
			if (rr < br) {
				for (int i = rr; i < br; i++) {
					score += state.placeGreedy(i, L_sorted[i], rnd, ra[i]);
				}
				br = rr;
			}
			if (di < ti) {
				di += dd;
				cerr << score << endl;
			}
			cnt++;
			a = rnd.nextInt(rr, K - 1);
			//if ((--a) == -1)a = -1;
			score += state.erase(a, L_sorted[a]);
			score += state.placeGreedy(a, L_sorted[a], rnd, ra[a]);
			//if (state.rects[a].o == VERTICAL) {
			//	if (state.rects[a].topY < 30 && state.rects[a].topY + L_sorted[a] - 1 >= 30) {
			//		cerr << state.rects[a].leftX << " " << state.rects[a].topY << " " << L_sorted[a] << endl;
			//		//assert(false);
			//	}
			//}
			//else if (state.rects[a].o == HORIZONTAL) {
			//	if (state.rects[a].leftX < 30 && state.rects[a].leftX + L_sorted[a] - 1 >= 30) {
			//		cerr << state.rects[a].leftX << " " << state.rects[a].topY << " " << L_sorted[a] << endl;
			//	//	assert(false);
			//	}
			//}

		}
		cerr << score << endl;
		cerr << "cnt = " << cnt << endl;
	}
	void greedy3(double timelimit) {
		int score = state.calcScore();
		double ti;
		int a;
		int cnt = 0;
		cerr << score << endl;
		cerr << state.calcScore() << endl;

		a = K - 1;
		double st = timer.get();
		double di = st;
		cerr << "st=" << st << endl;
		double dd = (timelimit - st)*0.1;
		double rem;
		int br = 500;
		int rr;
		double m = 1.0 * timelimit;
		while (true) {
			ti = timer.get();
			if (ti > timelimit) {
				break;
			}

			if (di < ti) {
				di += dd;
				cerr << score << " " << rr << endl;
			}
			cnt++;
			a = rnd.nextInt(K);
			//a = rnd.nextInt(rr, rr + 150);
			//if ((--a) == -1)a = -1;
			score += state.erase(a, L_sorted[a]);
			score += state.placeGreedy(a, L_sorted[a], rnd);
		}
		cerr << score << endl;
		cerr << "cnt = " << cnt << endl;
	}
	void greedy4(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 cnt = 0;
		cerr << score << endl;
		cerr << state.calcScore() << endl;

		a = K - 1;
		double st = timer.get();
		double di = st;
		cerr << "st=" << st << endl;
		double dd = (timelimit - st)*0.1;
		double rem;
		int br = 500;
		int rr;
		double m = 1.0 * timelimit;
		while (true) {
			ti = timer.get();
			if (ti > timelimit) {
				break;
			}
			rem = (m - ti) / (m - st);
			if (rem > 0) {
				rr = 350 * rem;
				if (rr < br) {
					for (int i = br - 1; i >= rr; i--) {
						score += state.placeGreedyH(i, L_sorted[i], rnd);
					}
					br = rr;
				}
			}

			if (di < ti) {
				di += dd;
				cerr << score << " " << rr << endl;
			}
			cnt++;
			a = rnd.nextInt(rr, K - 1);
			//a = rnd.nextInt(rr, rr + 150);
			//if ((--a) == -1)a = -1;
			score += state.erase(a, L_sorted[a]);
			score += state.placeGreedyH(a, L_sorted[a], rnd);
		}
		cerr << score << endl;
		cerr << "cnt = " << cnt << endl;
	}
	void solve() {
		init();
		//greedy(0.1);
		//greedy2(0.95);
		SA(0.95);
		//greedy4(10);
		//greedy3(0.95);

		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