結果

問題 No.5002 stick xor
ユーザー iwashi31iwashi31
提出日時 2018-05-26 03:41:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 871 ms / 1,000 ms
コード長 6,618 bytes
コンパイル時間 30,608 ms
実行使用メモリ 1,548 KB
スコア 42,639
最終ジャッジ日時 2018-05-26 03:41:56
ジャッジサーバーID
（参考情報） 		judge7 /
純コード判定しない問題か言語
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

//
// ver 1.1
//

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

#define YOKO 0
#define TATE 1

using namespace std;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

int N, K;
vector<int> L;
bool board[60][60], cboard[60][60];

int firstWhites;

class Point {
public:
	int x, y;
	Point() {}
	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
};

bool ansBoard[60][60];
class Answer {
public:
	int score;
	vector<pair<Point, int>> v;

	int calcScore() {
		memset(ansBoard, 0, sizeof ansBoard);
		rep(y, N) rep(x, N) ansBoard[y][x] = cboard[y][x];
		rep(i, K) {
			Point p = v[i].first;
			int dir = v[i].second;
			rep(j, L[i]) {
				ansBoard[p.y][p.x] ^= 1;
				p.x += dx[dir];
				p.y += dy[dir];
			}
		}
		score = -firstWhites;
		rep(y, N) rep(x, N) score += !ansBoard[y][x];
		return score;
	}

	void output() {
		rep(i, K) {
			Point p = v[i].first;
			int dir = v[i].second;
			p.x++; p.y++;
			cout << p.y << " " << p.x << " " << p.y + (L[i] - 1) * dy[dir] << " " << p.x + (L[i] - 1) * dx[dir] << endl;
		}
	}
};

bool inBoard(int x, int y) {
	return x >= 0 && x < N && y >= 0 && y < N;
}

unsigned long randXor() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

long long beginCycle;
unsigned long long getCycle() {
	unsigned int low, high;
	__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
	return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}

double getTime() {
	return (double)(getCycle() - beginCycle) / 2500000000;
}

void input() {
	cin >> N >> K;
	inputVector(L, K);

	vector<string> strBoard;
	inputVector(strBoard, N);

	rep(y, N) rep(x, N) {
		if (strBoard[y][x] == '1') {
			board[y][x] = 1;
			cboard[y][x] = 1;
		} else {
			firstWhites++;
		}
	}
}

int trySwap(int x, int y, int len, int dir) {
	int ret = 0;
	rep(i, len) {
		if (board[y][x]) ret++;
		else ret--;
		x += dx[dir];
		y += dy[dir];
	}
	return ret;
}

int doSwap(int x, int y, int len, int dir) {
	int ret = 0;
	rep(i, len) {
		if (board[y][x]) ret++;
		else ret--;
		board[y][x] ^= 1;
		x += dx[dir];
		y += dy[dir];
	}
	return ret;
}

void trySlideIfBetter(Answer &ans, int idx) {
	int maxDiff = 0;
	int maxScore = 0;
	int score = 0;
	int dir = ans.v[idx].second;

	Point headP = ans.v[idx].first;
	Point tailP = ans.v[idx].first;
	headP.x += dx[dir] * L[idx];
	headP.y += dy[dir] * L[idx];
	REP(i, 1, (L[idx] + 1) / 2) {
		if (!inBoard(headP.x, headP.y)) break;
		score += board[headP.y][headP.x];
		score -= !board[tailP.y][tailP.x];
		if (score > maxScore) {
			maxDiff = i;
			maxScore = score;
		}
		headP.x += dx[dir];
		headP.y += dy[dir];
		tailP.x += dx[dir];
		tailP.y += dy[dir];
	}

	headP = ans.v[idx].first;
	tailP = ans.v[idx].first;
	headP.x -= dx[dir];
	headP.y -= dy[dir];
	tailP.x += dx[dir] * (L[idx] - 1);
	tailP.y += dy[dir] * (L[idx] - 1);
	REP(i, 1, (L[idx] + 1) / 2) {
		if (!inBoard(headP.x, headP.y)) break;
		score += board[headP.y][headP.x];
		score -= !board[tailP.y][tailP.x];
		if (score > maxScore) {
			maxDiff = -i;
			maxScore = score;
		}
		headP.x -= dx[dir];
		headP.y -= dy[dir];
		tailP.x -= dx[dir];
		tailP.y -= dy[dir];
	}

	if (maxDiff > 0) {
		headP = ans.v[idx].first;
		tailP = ans.v[idx].first;
		headP.x += dx[dir] * L[idx];
		headP.y += dy[dir] * L[idx];
		rep(i, maxDiff) {
			board[headP.y][headP.x] ^= 1;
			board[tailP.y][tailP.x] ^= 1;
			ans.v[idx].first.x += dx[dir];
			ans.v[idx].first.y += dy[dir];
			headP.x += dx[dir];
			headP.y += dy[dir];
			tailP.x += dx[dir];
			tailP.y += dy[dir];
		}
	} else if (maxDiff < 0) {
		headP = ans.v[idx].first;
		tailP = ans.v[idx].first;
		headP.x -= dx[dir];
		headP.y -= dy[dir];
		tailP.x += dx[dir] * (L[idx] - 1);
		tailP.y += dy[dir] * (L[idx] - 1);
		rep(i, maxDiff) {
			board[headP.y][headP.x] ^= 1;
			board[tailP.y][tailP.x] ^= 1;
			ans.v[idx].first.x -= dx[dir];
			ans.v[idx].first.y -= dy[dir];
			headP.x -= dx[dir];
			headP.y -= dy[dir];
			tailP.x -= dx[dir];
			tailP.y -= dy[dir];
		}
	}
}

void tryMoveIfBetter(Answer &ans, int idx, int tx, int ty, int dir) {
	if (!inBoard(tx, ty) || !inBoard(tx + dx[dir] * L[idx], ty + dy[dir] * L[idx])) return;
	Point nowP = ans.v[idx].first;
	int nowDir = ans.v[idx].second;
	int score = doSwap(nowP.x, nowP.y, L[idx], nowDir);
	score += trySwap(tx, ty, L[idx], dir);
	if (score >= 0) {
		doSwap(tx, ty, L[idx], dir);
		ans.v[idx].first.x = tx;
		ans.v[idx].first.y = ty;
		ans.v[idx].second = dir;
	} else {
		doSwap(nowP.x, nowP.y, L[idx], nowDir);
	}
}

Answer solve() {
	Answer ans;
	rep(i, K) {
		int maxScore = -1000000;
		Point maxP;
		int maxDir;
		rep(y, N) rep(x, N - L[i] + 1) {
			int score = trySwap(x, y, L[i], YOKO);
			if (score > maxScore) {
				maxScore = score;
				maxP.x = x;
				maxP.y = y;
				maxDir = YOKO;
			}
		}
		rep(y, N - L[i] + 1) rep(x, N) {
			int score = trySwap(x, y, L[i], TATE);
			if (score > maxScore) {
				maxScore = score;
				maxP.x = x;
				maxP.y = y;
				maxDir = TATE;
			}
		}

		ans.v.push_back(mp(maxP, maxDir));
		doSwap(maxP.x, maxP.y, L[i], maxDir);
	}

	double nowTime = getTime();
	while (nowTime < 0.9) {
		int idx = randXor() % K;

		//trySlideIfBetter(ans, idx);

		int dir = randXor() % 2;
		int tx = randXor() % (dir == YOKO ? N - L[idx] + 1 : N);
		int ty = randXor() % (dir == TATE ? N - L[idx] + 1 : N);
		tryMoveIfBetter(ans, idx, tx, ty, dir);

		int nowdir = ans.v[idx].second;
		int diff = randXor() % (L[idx] + 1) / 2 + 1;
		tryMoveIfBetter(ans, idx, tx - dx[dir] * diff, ty - dy[dir] * diff, nowdir);
		tryMoveIfBetter(ans, idx, tx + dx[dir] * diff, ty + dy[dir] * diff, nowdir);

		nowTime = getTime();
	}

	return ans;
}

int main(int argc, char* argv[]) {
	beginCycle = getCycle();

	input();

	Answer ans = solve();

	if (argc > 1 && string(argv[1]) == "debug") {
		cout << ans.calcScore() << endl;
	} else {
		ans.output();
	}

    return 0;
}
0