#261630 (C++11) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: pirozhki
• 提出日時: 2018-05-30 20:29:12
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 36 ms / 1,000 ms
• コード長: 2,127 bytes
• コンパイル時間: 2,493 ms
• 実行使用メモリ: 1,532 KB
• スコア: 39,733
• 最終ジャッジ日時: 2018-05-30 20:29:16
• ジャッジサーバーID （参考情報）: judge7 /

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	25 ms; 1,528 KB
testcase_01	AC	26 ms; 1,528 KB
testcase_02	AC	25 ms; 1,528 KB
testcase_03	AC	26 ms; 1,528 KB
testcase_04	AC	26 ms; 1,528 KB
testcase_05	AC	26 ms; 1,524 KB
testcase_06	AC	26 ms; 1,524 KB
testcase_07	AC	27 ms; 1,524 KB
testcase_08	AC	26 ms; 1,528 KB
testcase_09	AC	26 ms; 1,528 KB
testcase_10	AC	26 ms; 1,528 KB
testcase_11	AC	25 ms; 1,532 KB
testcase_12	AC	26 ms; 1,524 KB
testcase_13	AC	26 ms; 1,528 KB
testcase_14	AC	26 ms; 1,528 KB
testcase_15	AC	27 ms; 1,524 KB
testcase_16	AC	26 ms; 1,524 KB
testcase_17	AC	27 ms; 1,528 KB
testcase_18	AC	26 ms; 1,524 KB
testcase_19	AC	26 ms; 1,532 KB
testcase_20	AC	26 ms; 1,524 KB
testcase_21	AC	33 ms; 1,528 KB
testcase_22	AC	26 ms; 1,524 KB
testcase_23	AC	27 ms; 1,532 KB
testcase_24	AC	27 ms; 1,532 KB
testcase_25	AC	36 ms; 1,528 KB
testcase_26	AC	33 ms; 1,528 KB
testcase_27	AC	26 ms; 1,528 KB
testcase_28	AC	26 ms; 1,528 KB
testcase_29	AC	26 ms; 1,528 KB
testcase_30	AC	26 ms; 1,532 KB
testcase_31	AC	26 ms; 1,528 KB

ソースコード

#include <iostream>
#include <bitset>
#include <array>
#include <algorithm>

using namespace std;

struct Pos {
	int x;
	int y;
};

enum Dir { DOWN, RIGHT };

struct Op{
	int idx;
	int len;
	pair<Pos, Dir> pos;
};

const int N = 60;

void Transpose(const array<bitset<N>, N>& arr, array<bitset<N>, N>& arr_t) {
	for (int i = 0; i < arr.size(); i++) {
		for (int j = 0; j < arr.size(); j++) {
			arr_t[j][i] = arr[i][j];
		}
	}
}

int main() {
	array<bitset<N>, N> arr, arr_t;
	array<Op, 500> ops;

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		Op p;
		p.idx = i;
		cin >> p.len;
		ops[i] = p;
	}

	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = (s[j] == '0' ? 0 : 1);
		}
	}

	Transpose(arr, arr_t);
	std::sort(ops.begin(), ops.end(), [](const Op& l, const Op& r) { return l.len > r.len; });

	for (Op& op : ops) {
		bitset<N> bs;
		for (int i = 0; i < op.len; i++) {
			bs[i] = 1;
		}

		int best_e = 0;
		pair<Pos, Dir> best_pos;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N - (op.len-1); j++) {
				int e_x = (arr[i] & (bs << j)).count();	// 長方形内の黒の数
				int e_y = (arr_t[i] & (bs << j)).count();
				int e = max(e_x, e_y);
				if (e > best_e) {
					best_e = e;
					if (e_x > e_y) {
						best_pos = make_pair(Pos{ j, i }, RIGHT);
					}
					else {
						best_pos = make_pair(Pos{ i, j }, DOWN);
					}

				}
			}
		}
		// 操作を適用
		switch (best_pos.second) {
		case Dir::RIGHT:
			arr[best_pos.first.y] ^= bs << best_pos.first.x;
			Transpose(arr, arr_t);
			break;
		case Dir::DOWN:
			arr_t[best_pos.first.x] ^= bs << best_pos.first.y;
			Transpose(arr_t, arr);
			break;
		}
		op.pos = best_pos;
	}

	std::sort(ops.begin(), ops.end(), [](const Op& l, const Op& r) { return l.idx < r.idx; });

	for (Op op : ops) {
		int x1 = op.pos.first.x;
		int y1 = op.pos.first.y;
		int x2 = x1;
		int y2 = y1;
		switch (op.pos.second) {
		case Dir::RIGHT:
			x2 += (op.len-1);
			break;
		case Dir::DOWN:
			y2 += (op.len-1);
			break;
		}
		cout << y1+1 << " " << x1+1 << " " << y2+1 << " " << x2+1 << endl;
	}

	return 0;
}