#260492 (C++14) No.5002 stick xor

• 問題: No.5002 stick xor
• ユーザー: e869120
• 提出日時: 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

ソースコード

#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;
}