QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471827#6376. LaLa and LampZ_drjWA 1ms5676kbC++141.7kb2024-07-11 09:41:482024-07-11 09:41:48

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 09:41:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5676kb
  • [2024-07-11 09:41:48]
  • 提交

answer

#include <cstdio>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>

using i64 = long long;

const int N = 2005;

int n;
int st[N][N], now[N][N];
int ans[N * 2];

void solve(){
	int now1 = 1, now2 = 2 * n;
	int x = n, y = n;
	for (int i = 1;i <= n; i++) {
		if (now1 == now2) {
			break;
		}
		ans[now1] = now[x][y] ^ ans[now2], --now2;
		if (now1 == now2) {
			break;
		}
		--x, --y;
		ans[now2] = now[x][y] ^ ans[now1], ++now1;
		++x;
	}
}

bool check(){
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n - i + 1; j++) {
			now[j + i - 1][j] = st[j + i - 1][j] ^ ans[i];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			now[j][i] ^= ans[i + n];
		}
	}

	for (int i = 1; i <= n; i++) {
		bool ok = true;
		for (int j = 1; j <= n; j++) {
			if (now[i][j] != 0) {
				ok = false;
				break;
			}
		}

		if (!ok) {
			continue;
		}

		for (int j = 1; j <= n; j++) {
			if (now[i][j] != 1) {
				return false;
			}
		}
	}

	return true;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);

	std::cin >> n;
	
	for (int i = 1; i <= n; i++) {
		std::string s; std::cin >> s;
		for (int j = 0; j < (int)s.size(); j++) {
			st[i][j + 1] = s[j] - '0';
		}
	}

	for (int i = 0; i < (1 << 2); i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 1; k <= n + j - 1; k++) {
				now[n + j - 1][k] = st[n + j - 1][k] ^ (i >> j & 1);
			}
		}

		for (int j = 0; j < 2; j++) {
			ans[n * 2] = j;
			solve();
			if (check()) {
				puts("Yes");
				return 0;
			}
		}
	}

	puts("No");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5660kb

input:

6
0
00
000
0110
00100
000000

output:

Yes

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 5636kb

input:

2
0
11

output:

Yes

result:

ok answer is YES

Test #3:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

3
1
10
011

output:

Yes

result:

ok answer is YES

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 5664kb

input:

4
1
11
101
0101

output:

Yes

result:

wrong answer expected NO, found YES