結果

問題 No.5002 stick xor
コンテスト
ユーザー e869120
提出日時 2018-05-26 10:22:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 39 ms / 1,000 ms
コード長 1,802 bytes
コンパイル時間 2,938 ms
実行使用メモリ 1,532 KB
スコア 40,509
最終ジャッジ日時 2018-05-26 10:22:23
ジャッジサーバーID
（参考情報） 		judge6 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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