QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#391505#6432. Puzzle in InazumadykwWA 2ms3916kbC++203.3kb2024-04-16 16:48:462024-04-16 16:48:47

Judging History

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

  • [2024-04-16 16:48:47]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3916kb
  • [2024-04-16 16:48:46]
  • 提交

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 != 0) {
        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: 3632kb

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: 3588kb

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: 3584kb

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: 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: 3744kb

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: 3580kb

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: 3648kb

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: 3724kb

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: 2ms
memory: 3916kb

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: 3608kb

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: 3780kb

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: 3752kb

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: 3784kb

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: 3600kb

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: 3748kb

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
Wrong Answer
time: 0ms
memory: 3608kb

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:

-1

result:

wrong answer Wrong Answer!