QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#391492 | #6432. Puzzle in Inazuma | dykw | RE | 0ms | 3840kb | C++20 | 3.3kb | 2024-04-16 16:44:15 | 2024-04-16 16:44:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
vector<long double> solve(vector<vector<long double>> a) {
int n = a.size();
for (int i = 0; i < n; ++i) {
int mx = i;
for (int j = i + 1; j < n; ++j) {
if (fabs(a[j][i]) > fabs(a[mx][i])) mx = j;
}
a[i].swap(a[mx]);
for (int j = 0; j < n; ++j) {
if (j != i) {
long double t = a[j][i] / a[i][i];
for (int k = i + 1; k <= n; ++k) a[j][k] -= a[i][k] * t;
}
}
}
vector<long double> ret;
for (int i = 0; i < n; ++i) {
ret.push_back(a[i][n] / a[i][i]);
}
return ret;
}
int main() {
int n;
cin >> n;
vector f(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
cin >> f[i][j];
f[j][i] = f[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int x;
cin >> x;
f[i][j] -= x;
f[j][i] -= x;
}
}
vector<array<int, 5>> ans;
auto add = [&](int a, int b, int c, int d, int x) {
f[a][b] += x, f[b][a] += x;
f[a][c] += x, f[c][a] += x;
f[a][d] += x, f[d][a] += x;
f[b][c] -= x, f[c][b] -= x;
f[b][d] -= x, f[d][b] -= x;
f[c][d] -= x, f[d][c] -= x;
ans.push_back({a, b, c, d, x});
};
for (int i = 4; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (f[i][j] % 2 == 1) {
add(i, j, 0, 1, 1);
}
}
}
for (int i = 4; i < n; ++i) {
vector t = {0, 1, 2, 3};
sort(t.begin(), t.end(), [&](int x, int y) { return f[i][x] % 2 > f[i][y] % 2; });
int cnt = 0;
for (int x : t) cnt += f[i][x] % 2;
if (cnt == 1) {
add(i, t[0], t[1], t[2], 1);
add(i, t[0], t[1], t[3], 1);
add(i, t[0], t[2], t[3], 1);
} else if (cnt == 2) {
add(i, t[1], t[2], t[3], 1);
add(i, t[0], t[2], t[3], 1);
} else if (cnt == 3) {
add(i, t[0], t[1], t[2], 1);
} else if (cnt == 4) {
add(i, t[1], t[2], t[3], 1);
add(i, t[0], t[1], t[2], 1);
add(i, t[0], t[1], t[3], 1);
add(i, t[0], t[2], t[3], 1);
}
}
for (int i = 4; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
assert(f[i][j] % 2 == 0);
int v = f[i][j] / 2;
if (!v) continue;
add(i, j, 0, 1, -v);
add(j, i, 0, 1, -v);
}
for (int j = 0; j < 4; ++j) {
int x = (j + 1) % 4, y = (j + 2) % 4;
int v = f[i][j] / 2;
if (!v) continue;
add(i, j, x, y, -v);
add(j, i, x, y, -v);
}
}
vector<vector<int>> eq = {
{1, 1, -1, -f[0][1]},
{-1, 1, 1, -f[1][2]},
{1, -1, 1, -f[0][2]},
};
vector feq(3, vector<long double>(4));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 4; ++j) feq[i][j] = eq[i][j];
}
auto res = solve(feq);
vector<int> eans(3);
for (int i = 0; i < 3; ++i) eans[i] = res[i];
int w3 = -eans[0] - eans[1] + eans[2] + f[2][3];
int w4 = eans[0] - eans[1] - eans[2] + f[3][0];
int w6 = -eans[0] + eans[1] - eans[2] + f[1][3];
if (w3 != 0 || w4 != 0 || w6 != 0) {
cout << -1;
return 0;
}
for (int i = 0; i < 3; ++i) {
add(i, (i + 1) % 4, (i + 2) % 4, (i + 3) % 4, eans[i]);
}
cout << ans.size() << '\n';
for (auto [a, b, c, d, x] : ans) {
cout << a + 1 << ' ' << b + 1 << ' ' << c + 1 << ' ' << d + 1 << ' ' << x << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
4 0 1 1 0 0 1 1 0 0 1 1 0
output:
3 1 2 3 4 0 2 3 4 1 1 3 4 1 2 0
result:
ok n=4
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
4 3 3 3 0 0 0 0 0 0 3 3 3
output:
3 1 2 3 4 -3 2 3 4 1 0 3 4 1 2 0
result:
ok n=4
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
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: 3612kb
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: 3588kb
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: 3840kb
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: -100
Runtime Error
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...