QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #355923 | #6432. Puzzle in Inazuma | PorNPtree | RE | 1ms | 3920kb | C++14 | 5.4kb | 2024-03-17 13:52:37 | 2024-03-17 13:52:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, a[N][N];
vector< pair< pair< pair<int, int>, pair<int, int> >, int> > res;
void input()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
scanf("%d", &a[i][j]);
}
}
int s = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
int x;
scanf("%d", &x);
a[i][j] = x - a[i][j];
a[j][i] = a[i][j];
s += a[i][j];
}
}
if (s) {
puts("-1");
exit(0);
}
return;
}
void add(int a, int b, int c, int d, int e)
{
res.push_back({{{a, b}, {c, d}}, e});
e = -e;
::a[a][b] += e, ::a[a][c] += e, ::a[a][d] += e;
::a[b][c] -= e, ::a[b][d] -= e, ::a[c][d] -= e;
::a[b][a] += e, ::a[c][a] += e, ::a[d][a] += e;
::a[c][b] -= e, ::a[d][b] -= e, ::a[d][c] -= e;
return;
}
void tmodify(int a, int b, int c, int d, int e, int v)
{
add(d, a, b, e, -v);
add(d, a, b, c, v);
add(e, a, c, d, v);
add(e, a, b, c, -v);
return;
}
void modify(int a, int b, int c, int d, int e, int f, int v)
{
tmodify(a, b, c, d, e, v);
tmodify(a, b, c, f, e, -v);
return;
}
void modify(int a, int d, int f, int v)
{
int b = 0, c = 0, e = 0;
for (int i = 1; i <= n; ++i) {
if (i != a && i != d && i != f) {
if (!b) {
b = i;
} else if (!c) {
c = i;
} else if (!e) {
e = i;
}
}
}
if (n == 5) {
e = c, c = b, b = f;
assert(!(v & 1));
v = -v / 2;
tmodify(a, b, c, d, e, v);
tmodify(a, b, e, d, c, v);
return;
}
modify(a, b, c, d, e, f, v);
return;
}
void print()
{
printf("%d\n", (int)res.size());
for (int i = 0; i < (int)res.size(); ++i) {
printf("%d %d %d %d %d\n", res[i].first.first.first, res[i].first.first.second, res[i].first.second.first, res[i].first.second.second, res[i].second);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
assert(!a[i][j]);
}
}
return;
}
int b[N][N];
signed main()
{
input();
if (n >= 6) {
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (a[i][j]) {
int z = -1;
for (int k = i + 1; k <= n; ++k) {
if (k != i && k != j) {
z = k;
break;
}
}
modify(j, i, z, a[i][j]);
}
}
}
print();
} else if (n == 5) {
for (int z = 0; z < 1024; ++z) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
b[i][j] = a[i][j];
}
}
res.clear();
int C = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (j != i) {
int ta = 0, tb = 0, tc = 0;
for (int k = 1; k <= n; ++k) {
if (k != i && k != j) {
if (!ta) {
ta = k;
} else if (!tb) {
tb = k;
} else if (!tc) {
tc = k;
}
}
}
add(i, ta, tb, tc, (z >> (C++)) & 1);
}
}
}
int flag = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
flag &= !(a[i][j] & 1);
}
}
if (!flag) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
a[i][j] = b[i][j];
}
}
continue;
}
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (a[i][j]) {
int z = -1;
for (int k = i + 1; k <= n; ++k) {
if (k != i && k != j) {
z = k;
break;
}
}
modify(j, i, z, a[i][j]);
}
}
}
print();
}
puts("-1");
} else {
if (a[1][2] + a[3][4] || a[1][3] + a[2][4] || a[1][4] + a[2][3]) {
puts("-1");
} else {
if (((a[1][2] + a[1][3]) & 1) || ((a[1][2] + a[1][4]) & 1) || ((a[1][3] + a[1][4]) & 1)) {
puts("-1");
} else {
add(2, 1, 3, 4, -(a[1][3] + a[1][4]) / 2);
add(3, 1, 2, 4, -(a[1][2] + a[1][4]) / 2);
add(4, 1, 2, 3, -(a[1][2] + a[1][3]) / 2);
print();
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3908kb
input:
4 0 1 1 0 0 1 1 0 0 1 1 0
output:
3 2 1 3 4 1 3 1 2 4 0 4 1 2 3 0
result:
ok n=4
Test #2:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
4 3 3 3 0 0 0 0 0 0 3 3 3
output:
3 2 1 3 4 3 3 1 2 4 3 4 1 2 3 3
result:
ok n=4
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
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: 3688kb
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: 1ms
memory: 3808kb
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: 3572kb
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: 1ms
memory: 3764kb
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: 1ms
memory: 3832kb
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: 1ms
memory: 3804kb
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: 3892kb
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: 3628kb
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: 1ms
memory: 3772kb
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: 3572kb
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: 1ms
memory: 3812kb
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: 1ms
memory: 3764kb
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: 1ms
memory: 3724kb
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: -100
Runtime Error
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