結果

問題 No.5002 stick xor
コンテスト
ユーザー ats5515
提出日時 2018-05-26 02:27:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 959 ms / 1,000 ms
コード長 7,443 bytes
コンパイル時間 33,561 ms
実行使用メモリ 2,172 KB
スコア 45,187
最終ジャッジ日時 2018-05-26 02:27:44
ジャッジサーバーID
（参考情報） 		judge8 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 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);
		}
	}

	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 State {
	Rectangle rects[K];
	int grid[N][N];
	void init(int _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 l;
		int sc;
		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++;
			}
		}
		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///////
	int grid[N][N];
	int L[K];
	int L_sorted[K];
	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;
		for (int i = 0; i < 1000; i++) {
			gen.next();
		}
		for (int i = 0; i < K; i++) {
			L[i] = gen.nextInt(25) + 1;
		}
		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 << 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;
	}
	void init() {
		//generateTestCase(0);
		inputFromStdin();
		state.init(grid);
		for (int i = 0; i < K; i++) {
			L_sorted[i] = L[i];
		}
		sort(L_sorted, L_sorted + K);

	}
	void greedy() {
		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;
		double di;
		a = K - 1;
		double st = timer.get();
		cerr << "st=" << st << endl;
		double timelimit = 0.95;
		double rem;
		while (true) {
			ti = timer.get();
			if (ti > timelimit) {
				break;
			}
			rem = (timelimit - ti) / (timelimit - st);
			if (di < ti) {
				di += 0.1;
				cerr << score << endl;
			}
			cnt++;
			a = rnd.nextInt(K);
			//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 solve() {
		init();
		greedy();
		outputDebugInfo();
	}
};


int main() {
	Solver solver;
	solver.solve();
	solver.outputResult();
}
0