QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#683350#6432. Puzzle in InazumaAndycraftRE 1ms3984kbC++204.0kb2024-10-27 20:25:422024-10-27 20:25:42

Judging History

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

  • [2024-10-27 20:25:42]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3984kb
  • [2024-10-27 20:25:42]
  • 提交

answer

#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
template <class T> using Arr = std::vector<T>;
typedef long long LL;

const int MAXN = 105;
int g[MAXN][MAXN], h[MAXN][MAXN];
int n;

void dfs(int now, int dep, const int &m, Arr<Arr<int>> &v) {
	static Arr<int> buf;
	if (dep == 4) {
		v.push_back(buf);
		return;
	}
	for (int i = now; i <= m; ++i) {
		buf.push_back(i);
		dfs(i + 1, dep + 1, m, v);
		buf.pop_back();
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin >> n;
	LL sum = 0;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			std::cin >> g[i][j];
			g[j][i] = g[i][j];
			sum += g[i][j];
		}
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j) {
			std::cin >> h[i][j];
			h[j][i] = h[i][j];
			sum -= h[i][j];
		}
	if (sum != 0)
		return puts("-1"), 0;
	Arr<Arr<int>> ans;
	auto act = [&](int a, int b, int c, int d, int x) {
		assert(a != b && a != c && a != d && b != c && b != d && c != d);
		ans.push_back({a, b, c, d, x});
		g[a][b] += x;
		g[a][c] += x;
		g[a][d] += x;
		g[b][c] -= x;
		g[c][d] -= x;
		g[b][d] -= x;

		g[b][a] += x;
		g[c][a] += x;
		g[d][a] += x;
		g[c][b] -= x;
		g[d][c] -= x;
		g[d][b] -= x;
	};
	auto mex = [&](Arr<int> v) { std::ranges::sort(v); v.erase(std::unique(v.begin(), v.end()), v.end()); for (int i = 0; i < (int)v.size(); ++i) if (v[i] != i) return i; return (int)v.size(); };
	auto cross_legacy = [&](int a, int b, int c, int d, int x) {
		assert(~x & 1);
		act(a, b, c, d, x / 2);
		act(b, a, c, d, x / 2);
	};
	auto cross = [&](int a, int b, int c, int d, int x) {
		assert(~x & 1);
		int u = mex({a - 1, b - 1, c - 1, d - 1}) + 1;
		int v = mex({a - 1, b - 1, c - 1, d - 1, u - 1}) + 1;
		cross_legacy(a, b, u, v, x);
		cross_legacy(u, v, c, d, x);
	};
	for (int i = n; i > 6; --i) {
		Arr<int> tp;
		for (int j = 1; j < i; ++j)
			if ((g[j][i] ^ h[j][i]) & 1)
				tp.push_back(j);
		int m = (int)tp.size();
		int j;
		for (j = 0; j + 3 <= m; j += 3)
			act(i, tp[j], tp[j + 1], tp[j + 2], 1);
		j -= 3;
		if (m == j + 1) {
			int u = mex({tp[j] - 1}) + 1;
			int v = mex({tp[j] - 1, u - 1}) + 1;
			int w = mex({tp[j] - 1, u - 1, v - 1}) + 1;
			act(i, tp[j], u, v, 1);
			act(i, tp[j], u, w, 1);
			act(i, tp[j], v, w, 1);
		} else if (m == j + 2) {
			int u = mex({tp[j] - 1, tp[j + 1] - 1}) + 1;
			int v = mex({tp[j] - 1, tp[j + 1] - 1, u - 1}) + 1;
			act(i, tp[j], u, v, 1);
			act(i, tp[j + 1], u, v, 1);
		} else
			assert(false);
	}

	int m = std::min(n, 6);
	Arr<Arr<int>> ch;
	dfs(1, 0, m, ch);
	int K = (int)ch.size();
	bool success = false;
	for (int S = 0; S < (1 << K); ++S) {
		for (int i = 0; i < K; ++i)
			if (S & (1 << i))
				for (int u = 0; u < 4; ++u)
					for (int v = u + 1; v < 4; ++v)
						g[ch[i][u]][ch[i][v]] ^= 1;

		bool fail = false;
		for (int i = 1; i < m; ++i)
			for (int j = i + 1; j <= m; ++j)
				if ((g[i][j] ^ h[i][j]) & 1) {
					fail = true;
					break;
				}
		for (int i = 0; i < K; ++i)
			if (S & (1 << i))
				for (int u = 0; u < 4; ++u)
					for (int v = u + 1; v < 4; ++v)
						g[ch[i][u]][ch[i][v]] ^= 1;
		if (!fail) {
			success = true;
			for (int i = 0; i < K; ++i)
				if (S & (1 << i))
					act(ch[i][0], ch[i][1], ch[i][2], ch[i][3], 1);
			break;
		}
	}
	if (!success)
		return puts("-1"), 0;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j)
			assert(~(g[i][j] ^ h[i][j]) & 1);
	if (n >= 6) {
		for (int i = n; i > 1; --i)
			for (int j = i - 1; j >= 1; --j)
				if (g[i][j] != h[i][j]) {
					assert(i != 2 || j != 1);
					int u = 1, v = 2;
					cross(i, j, u, v, h[i][j] - g[i][j]);
				}
	} else
		for (int i = n; i > 1; --i)
			for (int j = i - 1; j >= 1; --j)
				if (g[i][j] != h[i][j]) {
					// assert(i != 2 || j != 1);
					int u = mex({i - 1, j - 1}) + 1;
					int v = mex({i - 1, j - 1, u - 1}) + 1;
					cross_legacy(i, j, u, v, h[i][j] - g[i][j]);
				}
	// for (int i = 1; i < n; ++i)
	// 	for (int j = i + 1; j <= n; ++j)
	// 		assert(g[i][j] == h[i][j]);
	printf("%lu\n", ans.size());
	for (auto v : ans)
		printf("%d %d %d %d %d\n", v[0], v[1], v[2], v[3], v[4]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3728kb

input:

4
0 1 1
0 0
1
1 0 0
1 1
0

output:

5
1 2 3 4 1
4 2 1 3 1
2 4 1 3 1
4 1 2 3 -1
1 4 2 3 -1

result:

ok n=4

Test #2:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

4
3 3 3
0 0
0
0 0 0
3 3
3

output:

7
1 2 3 4 1
4 3 1 2 2
3 4 1 2 2
4 2 1 3 2
2 4 1 3 2
4 1 2 3 -2
1 4 2 3 -2

result:

ok n=4

Test #3:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

5
-12 15 -12 1
37 14 7
7 9
-11
12 5 1 13
-1 -4 -7
-5 -9
18

output:

-1

result:

ok n=5

Test #4:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

4
37 81 -38
-79 -8
-42
20 -55 80
-23 -43
37

output:

-1

result:

ok n=4

Test #5:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

5
-22 63 -23 7
-11 36 66
66 -77
36
-87 -17 95 -65
-93 53 63
-54 -56
-77

output:

-1

result:

ok n=5

Test #6:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

6
-59 77 100 -28 -80
-14 -19 34 0
-8 34 44
58 38
7
87 -53 -57 -79 86
-19 -97 -51 -29
42 -14 61
-6 25
-24

output:

-1

result:

ok n=6

Test #7:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10
96 -62 71 43 -41 62 37 -17 -73
-51 55 89 63 -17 81 98 78
-96 -70 -16 78 -63 49 86
20 -76 -21 8 -32 16
-93 45 -65 99 65
9 81 47 -2
-50 94 2
29 -77
77
67 -91 -97 -13 -75 -8 -79 21 -86
-44 -55 -92 19 -62 47 25 -88
-89 -10 1 94 -61 78 -70
8 30 -54 -9 19 -60
35 -21 -79 40 92
-56 -12 -56 2
-38 23 -31
2...

output:

-1

result:

ok n=10

Test #8:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

30
79 75 -71 -8 36 26 -38 -45 43 44 64 52 -23 -64 -73 97 -79 70 24 58 -9 11 14 58 -95 -88 -10 -80 -47
20 -55 86 89 -39 15 26 -32 38 -23 -30 -12 -4 81 39 -13 -43 -11 -38 -70 14 32 -67 -54 38 -80 -80 97
-49 -92 53 -94 -60 -77 -80 -11 75 51 43 52 -28 58 -26 71 -85 66 96 -61 52 -100 -49 93 92 -37 62
-55...

output:

-1

result:

ok n=30

Test #9:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

50
-47 49 10 46 -54 -70 -39 36 -1 100 -78 -27 23 43 15 -21 71 48 -82 95 85 -11 -99 35 -44 -31 70 -94 12 -45 -81 75 62 89 14 85 -82 -25 2 5 54 -25 -96 -30 -12 -70 13 -51 15
-48 -13 -53 49 19 -62 -15 -99 54 29 17 67 31 -58 80 -2 -97 -40 59 64 84 15 -32 76 -18 35 76 68 -69 47 51 -26 64 -70 71 14 -3 47 ...

output:

-1

result:

ok n=50

Test #10:

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

input:

100
-25 31 38 48 -19 32 87 -10 -30 -88 -79 98 -99 56 -52 -86 -89 51 77 -36 -52 72 -78 48 30 42 -45 84 -75 -71 -83 -48 92 -44 6 -83 -87 -82 -17 40 -44 82 64 -90 89 -34 88 10 -26 -84 -51 -29 86 -55 55 78 12 -38 -96 28 -78 52 -30 85 72 79 57 8 71 -68 -81 -21 14 44 -42 -26 42 95 20 -78 18 29 100 39 -19 ...

output:

-1

result:

ok n=100

Test #11:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

4
75 -69 93
78 24
-61
75 59 80
-50 31
-55

output:

-1

result:

ok n=4

Test #12:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4
44 -25 -81
84 8
95
-70 -21 82
32 28
74

output:

-1

result:

ok n=4

Test #13:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4
91 -18 -46
-80 -34
38
-25 18 -40
-35 86
-53

output:

-1

result:

ok n=4

Test #14:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

5
-16 92 -94 -83
-83 16 -74
75 3
-43
-28 45 -63 -100
-11 -39 -80
62 -14
21

output:

-1

result:

ok n=5

Test #15:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

5
-95 7 -3 76
57 -85 -98
-64 -28
70
5 48 -42 -99
-56 22 21
-51 74
-85

output:

-1

result:

ok n=5

Test #16:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

5
-10 31 33 -71
33 -49 4
72 -72
65
-74 55 20 41
61 62 -83
50 -1
-95

output:

-1

result:

ok n=5

Test #17:

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

input:

6
65 -33 2 -67 83
40 93 -28 86
54 -30 -11
56 40
-66
82 42 -32 -56 98
1 85 17 45
-12 -3 -50
-39 6
100

output:

61
1 2 3 5 1
1 2 3 6 1
1 2 4 5 1
1 3 4 5 1
2 3 4 5 1
6 5 3 4 83
5 6 3 4 83
3 4 1 2 83
4 3 1 2 83
6 4 3 5 -17
4 6 3 5 -17
3 5 1 2 -17
5 3 1 2 -17
6 3 4 5 -19
3 6 4 5 -19
4 5 1 2 -19
5 4 1 2 -19
6 2 3 4 -20
2 6 3 4 -20
3 4 1 2 -20
4 3 1 2 -20
6 1 3 4 7
1 6 3 4 7
3 4 1 2 7
4 3 1 2 7
5 4 3 6 -46
4 5 3 6...

result:

ok n=6

Test #18:

score: -100
Runtime Error

input:

10
-68 -48 27 80 89 -22 -43 34 43
-41 -4 -10 -90 -62 -11 83 22
-64 -77 84 -20 -56 -56 -79
49 -54 90 19 75 6
41 6 -33 -29 -39
45 -27 7 6
-57 93 -53
-46 -85
-37
40 -49 -32 -28 -16 -71 -97 -99 -67
6 34 -65 -97 95 -99 72 -34
81 32 16 -49 -71 61 -83
89 -23 2 35 -20 50
-14 32 83 31 -43
-15 74 -87 22
-56 -...

output:


result: