結果

問題 No.5002 stick xor
ユーザー e869120e869120
提出日時 2018-05-26 10:12:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 60 ms / 1,000 ms
コード長 1,800 bytes
コンパイル時間 4,248 ms
実行使用メモリ 1,532 KB
スコア 39,729
最終ジャッジ日時 2018-05-26 10:12:59
ジャッジサーバーID
(参考情報)
judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)

テストケース

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

ソースコード

diff #

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <functional>
using namespace std;

struct State {
	int a[66][66];
};

int N, K, L[509]; State S; vector<pair<int, int>>X; tuple<int, int, int, int>ans[509];

tuple<int, int, int, int> solve(int len) {
	int maxn = -1; tuple<int, int, int, int>maxid = make_tuple(0, 0, 0, 0);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N - len + 1; j++) {
			int sum = 0;
			for (int k = j; k < j + len; k++) sum += (1 - S.a[i][k]);
			if (maxn < sum) {
				maxn = sum;
				maxid = make_tuple(i, j, i, j + len - 1);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N - len + 1; j++) {
			int sum = 0;
			for (int k = j; k < j + len; k++) sum += (1 - S.a[k][i]);
			if (maxn < sum) {
				maxn = sum;
				maxid = make_tuple(j, i, j + len - 1, i);
			}
		}
	}
	return maxid;
}

void flip(int px, int py, int qx, int qy) {
	for (int i = px; i <= qx; i++) {
		for (int j = py; j <= qy; j++) S.a[i][j] ^= 1;
	}
}

int score() {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) ret += S.a[i][j];
	}
	return ret;
}

int main() {
	cin >> N >> K;
	for (int i = 1; i <= K; i++) { cin >> L[i]; X.push_back(make_pair(L[i], i)); }

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) { char c; cin >> c; if (c == '0') S.a[i][j] = 1; else S.a[i][j] = 0; }
	}
	sort(X.begin(), X.end(), greater<pair<int, int>>());

	for (int i = 0; i < X.size(); i++) {
		tuple<int, int, int, int>G = solve(X[i].first);
		ans[X[i].second] = G;
		flip(get<0>(G), get<1>(G), get<2>(G), get<3>(G));
	}
	for (int i = 1; i <= K; i++) {
		cout << get<0>(ans[i]) << " " << get<1>(ans[i]) << " " << get<2>(ans[i]) << " " << get<3>(ans[i]) << endl;
	}
	//cout << "#score = " << score() << endl;
	return 0;
}
0