結果

問題 No.5002 stick xor
ユーザー pirozhkipirozhki
提出日時 2018-05-31 21:39:03
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 61 ms / 1,000 ms
コード長 2,623 bytes
コンパイル時間 3,328 ms
実行使用メモリ 1,532 KB
スコア 40,989
最終ジャッジ日時 2018-05-31 21:39:09
ジャッジサーバーID
（参考情報） 		judge7 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <fstream>
#include <sstream>
#include <bitset>
#include <array>
#include <random>
#include <algorithm>
#include <type_traits>

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 |= static_cast<uint64_t>(1) << i;
		}

		double 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++) {
				bitset<N> mask_x = arr[i] & (bs << j);
				bitset<N> mask_y = arr_t[i] & (bs << j);
				double e_x = mask_x.count();
				double e_y = mask_y.count();

				// 上下につながったブロックがあったら評価を下げる
				if (i - 1 >= 0) {
					e_x -= ((arr[i - 1]) & mask_x).count() * 0.01;
					e_y -= ((arr_t[i - 1]) & mask_y).count() * 0.01;
				}
				if (i + 1 < N) {
					e_x -= ((arr[i + 1]) & mask_x).count() * 0.01;
					e_y -= ((arr_t[i + 1]) & mask_y).count() * 0.01;
				}

				double 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;
}
0