QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351809#8225. 最小值之和JCY_11 2ms5864kbC++144.0kb2024-03-12 15:17:132024-03-12 15:17:14

Judging History

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

  • [2024-03-12 15:17:14]
  • 评测
  • 测评结果:11
  • 用时:2ms
  • 内存:5864kb
  • [2024-03-12 15:17:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128;
using u128 = unsigned __int128;
template <typename T>
void chkmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
  if (y < x) x = y;
}
int ceil_div(int x, int y) { return x <= 0 ? x / y : (x - 1) / y + 1; }
int exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int d = exgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
constexpr int MAXN = 82;
int n, a[MAXN], f[MAXN][MAXN][MAXN], temp[MAXN], ans[MAXN];
void print(int l, int r, int v) {
  if (l == r) return;
  int x, y = 0;
  for (x = l; x < r; ++x) {
    if (x == l && x + 1 == r) {
      if (a[l] == a[r] && (a[l] - v) % (r - l) == 0) {
        y = (a[l] - v) / (r - l);
        break;
      }
    } else if (x == l) {
      if (f[l + 1][r][a[l] % (r - l - 1)] >= a[l] && (a[l] - v) % (r - l) == 0) {
        y = (a[l] - v) / (r - l);
        break;
      }
    } else if (x + 1 == r) {
      if (f[l][r - 1][a[r] % (r - l - 1)] >= a[r] && (a[r] - v) % (r - l) == 0) {
        y = (a[r] - v) / (r - l);
        break;
      }
    } else {
      int up = (x - l) / __gcd(x - l, r - x - 1) * (r - x - 1);
      for (y = 0; y < up; ++y) {
        if (f[l][x][(v + y * (r - l)) % (x - l)] >= v + y * (r - l) && 
            f[x + 1][r][(v + y * (r - l)) % (r - x - 1)] >= v + y * (r - l)) {
          break;
        }
      }
      if (y != up) break;
    }
  }
  assert(x != r);
  print(l, x, v + y * (r - l));
  print(x + 1, r, v + y * (r - l));
  for (int i = l; i < r; ++i) ans[i] += y;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  if (n == 1) {
    cout << (a[1] ? "No" : "Yes\n") << "\n";
    return 0;
  }
  memset(f, -1, sizeof(f));
  for (int l = n; l >= 1; --l) {
    for (int r = l + 1; r <= n; ++r) {
      for (int x = l; x < r; ++x) {
        if (x == l && x + 1 == r) {
          if (a[l] == a[r]) chkmax(f[l][r][a[l] % (r - l)], a[l]);
        } else if (x == l) {
          if (f[l + 1][r][a[l] % (r - l - 1)] >= a[l])
            chkmax(f[l][r][a[l] % (r - l)], a[l]);
        } else if (x + 1 == r) {
          if (f[l][r - 1][a[r] % (r - l - 1)] >= a[r])
            chkmax(f[l][r][a[r] % (r - l)], a[r]);
        } else {
          fill(temp, temp + r - l, -1);
          int sx, sy, d = exgcd(x - l, r - x - 1, sx, sy);
          sy = -sy;
          int coef = max(ceil_div(-sx, (r - x - 1) / d), ceil_div(-sy, (x - l) / d));
          sx += (r - x - 1) / d * coef;
          sy += (x - l) / d * coef;
          for (int i = 0; i < x - l; ++i) {
            if (f[l][x][i] == -1) continue;
            for (int j = 0; j < r - x - 1; ++j) {
              if (f[x + 1][r][j] == -1) continue;
              int c = f[l][x][i] - f[x + 1][r][j];
              if (c % d) continue;
              ll fst = f[l][x][i] - (ll)c / d * sx * (x - l);
              if (fst >= 0) chkmax(temp[fst % (r - l)], (int)fst);
            }
          }
          d = (x - l) / d * (r - x - 1);
          for (int s = 0, td = d % (r - l), up = __gcd(r - l, td); s < up; ++s) {
            auto nxt = [&](int v) {
              v -= td;
              return v < 0 ? v + r - l : v;
            };
            for (int turn = 0; turn < 2; ++turn) {
              for (int i = s, j = nxt(s);; i = j, j = nxt(j)) {
                chkmax(temp[j], temp[i] - d);
                if (j == s) break;
              }
            }
          }
          for (int i = 0; i < r - l; ++i) chkmax(f[l][r][i], temp[i]);
        }
      }
    }
  }
  if (f[1][n][0] == -1) {
    cout << "No\n";
    return 0;
  }
  cout << "Yes\n";
  print(1, n, 0);
  for (int i = 1; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
  return 0;
}
/*
g++ B.cpp -o B -std=c++14 -O2 -Wall -Wextra -Wshadow -g -fsanitize=address,undefined
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 1ms
memory: 5728kb

input:

5
14 14 12 13 13

output:

Yes
14 0 6 7

result:

ok The answer is correct.

Test #2:

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

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1

result:

ok The answer is correct.

Test #3:

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

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4

result:

ok The answer is correct.

Test #4:

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

input:

5
11 11 10 5 5

output:

Yes
6 5 0 5

result:

ok The answer is correct.

Test #5:

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

input:

5
10 10 10 4 4

output:

Yes
5 5 0 4

result:

ok The answer is correct.

Test #6:

score: 0
Accepted
time: 2ms
memory: 5784kb

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1

result:

ok The answer is correct.

Test #7:

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

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8

result:

ok The answer is correct.

Test #8:

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

input:

5
2 2 6 11 11

output:

Yes
2 0 3 8

result:

ok The answer is correct.

Test #9:

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

input:

5
10 10 8 5 5

output:

Yes
6 4 0 5

result:

ok The answer is correct.

Test #10:

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

input:

5
24 24 28 28 26

output:

Yes
6 6 9 7

result:

ok The answer is correct.

Test #11:

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

input:

5
5 5 22 31 31

output:

Yes
5 0 11 20

result:

ok The answer is correct.

Test #12:

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

input:

5
8 33 38 38 29

output:

Yes
2 11 16 9

result:

ok The answer is correct.

Test #13:

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

input:

5
16 16 4 12 12

output:

Yes
16 0 2 10

result:

ok The answer is correct.

Test #14:

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

input:

5
29 29 24 26 26

output:

Yes
29 0 12 14

result:

ok The answer is correct.

Test #15:

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

input:

5
0 33 33 32 32

output:

Yes
0 33 0 32

result:

ok The answer is correct.

Test #16:

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

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

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

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

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

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

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

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

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

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

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

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

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

input:

5
6 7 7 6 6

output:

Yes
3 4 0 6

result:

ok The answer is correct.

Test #23:

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

input:

5
25 25 24 20 20

output:

Yes
13 12 0 20

result:

ok The answer is correct.

Test #24:

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

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

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

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

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

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

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

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

score: 0
Accepted
time: 2ms
memory: 5812kb

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

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

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

score: 0
Accepted
time: 2ms
memory: 5768kb

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

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

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

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

input:

2
2 2

output:

Yes
2

result:

ok The answer is correct.

Test #33:

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

input:

1
0

output:

Yes


result:

ok The answer is correct.

Test #34:

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

input:

1
233

output:

No

result:

ok The answer is correct.

Subtask #2:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #35:

score: 15
Accepted
time: 0ms
memory: 5816kb

input:

8
16 16 8 8 9 9 6 6

output:

Yes
16 0 8 0 9 0 6

result:

ok The answer is correct.

Test #36:

score: 0
Accepted
time: 2ms
memory: 5784kb

input:

8
16 16 9 21 21 23 23 23

output:

Yes
16 0 3 15 1 10 10

result:

ok The answer is correct.

Test #37:

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

input:

8
10 10 15 15 15 10 10 5

output:

Yes
10 0 6 6 1 6 1

result:

ok The answer is correct.

Test #38:

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

input:

8
13 13 15 15 24 24 24 10

output:

Yes
13 0 7 2 9 9 2

result:

ok The answer is correct.

Test #39:

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

input:

8
5 13 16 25 25 24 4 4

output:

Yes
1 3 4 9 8 0 4

result:

ok The answer is correct.

Test #40:

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

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

Yes
654 1036 1 771 353 1 551

result:

ok The answer is correct.

Test #41:

score: -15
Runtime Error

input:

8
1386 1416 1416 1069 1069 390 645 645

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Test #77:

score: 0
Runtime Error

input:

49
28 28 28 24 37 37 33 36 36 29 43 43 41 41 29 48 51 51 44 49 50 50 9 9 15 18 18 3 17 17 9 13 17 17 13 13 0 6 6 16 21 25 25 19 7 19 19 17 4

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%