結果

問題 No.5002 stick xor
ユーザー pirozhkipirozhki
提出日時 2018-05-31 21:33:09
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,689 bytes
コンパイル時間 6,182 ms
実行使用メモリ 2,484 KB
スコア 0
最終ジャッジ日時 2018-05-31 21:33:16
ジャッジサーバーID
（参考情報） 		judge7 /
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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;

	ifstream ifs("test.txt", ios::binary);
	int n, k;
	ifs >> n >> k;
	for (int i = 0; i < k; i++) {
		Op p;
		p.idx = i;
		ifs >> p.len;
		ops[i] = p;
	}

	string s;
	for (int i = 0; i < n; i++) {
		ifs >> 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);
					}

				}
			}
		}
		cout << best_e << endl;
		// 操作を適用
		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