QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#353198#8225. 最小值之和yaoxi_std81 11ms4656kbC++143.8kb2024-03-13 23:05:462024-03-13 23:05:46

Judging History

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

  • [2024-03-13 23:05:46]
  • 评测
  • 测评结果:81
  • 用时:11ms
  • 内存:4656kb
  • [2024-03-13 23:05:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
  fprintf(stderr, "[%d] : " fmt "\n", __LINE__, ##__VA_ARGS__)
template <class _Tx, class _Ty>
inline void chkmin(_Tx& x, const _Ty& y) { if (y < x) x = y; }
template <class _Tx, class _Ty>
inline void chkmax(_Tx& x, const _Ty& y) { if (x < y) x = y; }
bool Mbe;
using ll = long long;
constexpr int N = 55;
int n, a[N], tmp[N], ans[N], f[N][N][N], pos[N][N][N];
ll div_c(ll n, ll d) {
  return n >= 0 ? (n + d - 1) / d : n / d;
}
ll div_f(ll n, ll d) {
  return n >= 0 ? n / d : (n - d + 1) / d;
}
int exgcd(int a, int b, int& x, int& y) {
  if (!b) return x = 1, y = 0, a;
  int d = exgcd(b, a % b, y, x);
  return y -= a / b * x, d;
}
void print(int l, int r, ll tot) {
  if (l > r) return;
  int vl = a[l - 1], vr = a[r];
  if (l == r) {
    ans[l] = vl - tot;
    return;
  }
  int k = r - l + 1;
  int p = pos[l][r][tot % k];
  if (p == l) {
    ans[p] = (vl - tot) / k;
    print(l + 1, r, tot + ans[p]);
    return;
  }
  if (p == r) {
    ans[p] = (vr - tot) / k;
    print(l, r - 1, tot + ans[p]);
    return;
  }
  ans[p] = (f[l][r][tot % k] - tot) / k;
  print(l, p - 1, tot + ans[p] * (r - p + 1));
  print(p + 1, r, tot + ans[p] * (p - l + 1));
}
bool Med;
int main() {
  // debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n, --n;
  for (int i = 0; i <= n; ++i) cin >> a[i];
  if (!n) return cout << (!a[0] ? "Yes" : "No") << '\n', 0;
  memset(f, -1, sizeof(f));
  for (int k = 1; k <= n; ++k) {
    for (int l = 1, r = k; r <= n; ++l, ++r) {
      int vl = a[l - 1], vr = a[r];
      if (k == 1) {
        if (vl == vr) f[l][r][0] = vl;
      } else {
        if (f[l + 1][r][vl % (k - 1)] >= vl) {
          if (f[l][r][vl % k] < vl) {
            f[l][r][vl % k] = vl;
            pos[l][r][vl % k] = l;
          }
        }
        if (f[l][r - 1][vr % (k - 1)] >= vr) {
          if (f[l][r][vr % k] < vr) {
            f[l][r][vr % k] = vr;
            pos[l][r][vr % k] = r;
          }
        }
        for (int p = l + 1; p < r; ++p) {
          fill(tmp, tmp + k, -1);
          int kl = p - l, kr = r - p;
          int cl, cr, d = exgcd(kl, kr, cl, cr);
          for (int bl = 0; bl < kl; ++bl) {
            if (f[l][p - 1][bl] == -1) continue;
            int dpl = f[l][p - 1][bl];
            for (int br = 0; br < kr; ++br) {
              if (f[p + 1][r][br] == -1) continue;
              int dpr = f[p + 1][r][br];
              if ((dpl - dpr) % d != 0) continue;
              ll xl = (ll)(dpl - dpr) / d * cl;
              ll xr = (ll)(dpr - dpl) / d * cr;
              assert(dpl - kl * xl == dpr - kr * xr);
              ll num = min(div_f(xl, kr / d), div_f(xr, kl / d));
              xl -= num * (kr / d), xr -= num * (kl / d);
              assert(xl >= 0 && xr >= 0);
              assert(dpl - kl * xl == dpr - kr * xr);
              ll val = dpl - kl * xl;
              if (val >= 0) chkmax(tmp[val % k], val);
            }
          }
          int step = kl * kr, gd = __gcd(step, k);
          for (int i = 0; i < gd; ++i) {
            for (int j = 0, t = i; j < k / gd * 2; ++j, t = (t + step) % k) {
              int nt = (t + step) % k;
              if (tmp[nt] != -1) chkmax(tmp[t], tmp[nt] - step);
            }
          }
          for (int i = 0; i < k; ++i) {
            if (f[l][r][i] < tmp[i]) {
              f[l][r][i] = tmp[i], pos[l][r][i] = p;
            }
          }
        }
      }
    }
  }
  if (f[1][n][0] == -1) return cout << "No\n", 0;
  cout << "Yes\n";
  print(1, n, 0);
  for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
  return 0;
}
/*
g++ -std=c++14 -O2 -o QOJ8225 QOJ8225.cpp
-Wall -Wextra -Wshadow
-fsanitize=address,undefined -g
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

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

input:

5
14 14 12 13 13

output:

Yes
5 3 3 4

result:

ok The answer is correct.

Test #2:

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

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

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

input:

5
11 11 10 5 5

output:

Yes
5 4 1 2

result:

ok The answer is correct.

Test #5:

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

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1

result:

ok The answer is correct.

Test #6:

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

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

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

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

input:

5
10 10 8 5 5

output:

Yes
5 3 1 2

result:

ok The answer is correct.

Test #10:

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

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

input:

5
5 5 22 31 31

output:

Yes
2 1 10 19

result:

ok The answer is correct.

Test #12:

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

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

input:

5
16 16 4 12 12

output:

Yes
13 1 1 9

result:

ok The answer is correct.

Test #14:

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

input:

5
29 29 24 26 26

output:

Yes
11 6 6 8

result:

ok The answer is correct.

Test #15:

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

input:

5
0 33 33 32 32

output:

Yes
0 13 10 12

result:

ok The answer is correct.

Test #16:

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

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

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

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

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

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

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

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

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

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

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

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

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

input:

5
6 7 7 6 6

output:

Yes
2 3 1 3

result:

ok The answer is correct.

Test #23:

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

input:

5
25 25 24 20 20

output:

Yes
8 7 5 5

result:

ok The answer is correct.

Test #24:

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

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

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

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

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

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

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

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

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

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

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

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

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

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

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

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

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

input:

2
2 2

output:

Yes
2

result:

ok The answer is correct.

Test #33:

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

input:

1
0

output:

Yes

result:

ok The answer is correct.

Test #34:

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

input:

1
233

output:

No

result:

ok The answer is correct.

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #35:

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

input:

8
16 16 8 8 9 9 6 6

output:

Yes
16 0 4 1 5 1 2

result:

ok The answer is correct.

Test #36:

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

input:

8
16 16 9 21 21 23 23 23

output:

Yes
9 2 1 6 4 6 6

result:

ok The answer is correct.

Test #37:

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

input:

8
10 10 15 15 15 10 10 5

output:

Yes
10 0 5 5 2 3 1

result:

ok The answer is correct.

Test #38:

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

input:

8
13 13 15 15 24 24 24 10

output:

Yes
7 1 9 1 9 9 2

result:

ok The answer is correct.

Test #39:

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

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

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

Yes
414 796 109 531 113 79 83

result:

ok The answer is correct.

Test #41:

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

input:

8
1386 1416 1416 1069 1069 390 645 645

output:

Yes
385 415 225 228 56 55 315

result:

ok The answer is correct.

Test #42:

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

input:

8
3377 3377 3164 3164 3570 3570 3365 3365

output:

Yes
665 452 452 452 724 519 519

result:

ok The answer is correct.

Test #43:

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

input:

8
28167709 33181201 33829300 33829300 21924091 26145199 28398185 28398185

output:

Yes
5213219 7719965 8368064 3132013 3132013 5242567 7495553

result:

ok The answer is correct.

Test #44:

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

input:

8
4726918 12793592 12793592 6681214 13995142 22020836 22566624 22566624

output:

Yes
675274 7113368 1000990 1000990 3438966 7451813 7997601

result:

ok The answer is correct.

Test #45:

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

input:

8
9146297 15736298 15736298 16471005 16471005 14187656 14187656 6001415

output:

Yes
1381492 3938409 2389763 4673114 2389764 2389765 857345

result:

ok The answer is correct.

Test #46:

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

input:

8
25115296 25115296 22120670 21035156 20603135 28703897 28703897 27553199

output:

Yes
6624695 3630069 3087312 2943305 2943305 7569035 6418337

result:

ok The answer is correct.

Test #47:

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

input:

8
22440147 22440147 22626721 22626721 22592252 22592252 19174074 19174074

output:

Yes
6005229 2739153 6191803 2739153 6157332 2739154 2739154

result:

ok The answer is correct.

Test #48:

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

input:

8
12 0 13 8 18 18 18 0

output:

No

result:

ok The answer is correct.

Test #49:

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

input:

8
3 23 13 18 26 12 25 25

output:

No

result:

ok The answer is correct.

Test #50:

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

input:

8
1353255 1004808 981534 1400692 1246708 409750 1177255 1177255

output:

No

result:

ok The answer is correct.

Test #51:

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

input:

8
96 96 99 99 4 94 39 36

output:

No

result:

ok The answer is correct.

Test #52:

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

input:

8
15 21 0 20 20 15 13 6

output:

No

result:

ok The answer is correct.

Test #53:

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

input:

8
2 1 0 2 6 6 5 1

output:

No

result:

ok The answer is correct.

Test #54:

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

input:

8
7 12 11 11 1 11 4 11

output:

No

result:

ok The answer is correct.

Test #55:

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

input:

8
18 3 27 27 19 10 6 6

output:

No

result:

ok The answer is correct.

Subtask #3:

score: 13
Accepted

Dependency #2:

100%
Accepted

Test #56:

score: 13
Accepted
time: 1ms
memory: 4348kb

input:

14
10 10 2 30 45 50 50 47 47 47 46 33 33 32

output:

Yes
9 1 0 3 6 10 7 5 8 7 3 5 4

result:

ok The answer is correct.

Test #57:

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

input:

14
0 19 19 16 16 4 0 36 36 36 36 31 31 26

output:

Yes
0 19 0 14 2 0 0 16 4 16 4 10 5

result:

ok The answer is correct.

Test #58:

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

input:

14
37 38 38 37 28 27 27 28 28 10 17 17 12 4

output:

Yes
10 11 10 7 0 27 0 28 0 3 9 4 1

result:

ok The answer is correct.

Test #59:

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

input:

14
13 27 33 33 30 30 31 31 20 20 25 25 24 24

output:

Yes
1 8 14 1 18 1 13 2 2 2 5 3 4

result:

ok The answer is correct.

Test #60:

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

input:

14
50 50 52 52 54 60 62 62 62 33 33 28 34 34

output:

Yes
26 2 28 2 9 11 12 12 2 9 2 3 9

result:

ok The answer is correct.

Test #61:

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

input:

14
5123 5321 5321 5600 5600 5161 5537 5537 5359 4679 4679 4128 4128 3029

output:

Yes
825 1023 324 1803 324 596 873 695 435 436 325 325 233

result:

ok The answer is correct.

Test #62:

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

input:

14
340 2315 2315 2251 2251 1200 1366 1366 2831 2831 2864 2864 2812 2680

output:

Yes
27 2002 26 1165 112 113 279 112 1745 112 724 672 606

result:

ok The answer is correct.

Test #63:

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

input:

14
681 810 2276 2390 2390 1189 2424 2424 2031 1180 2548 2620 2620 221

output:

Yes
56 99 832 946 55 135 949 556 123 132 816 888 17

result:

ok The answer is correct.

Test #64:

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

input:

14
37026886 40993600 44483477 44483477 41071802 57414984 57414984 60000010 60000010 64898381 64898381 63120240 63120240 58440430

output:

Yes
2848222 3178784 6668661 3178781 3187477 19530659 3187469 6394159 6394159 9212378 7434235 7434237 6082243

result:

ok The answer is correct.

Test #65:

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

input:

14
49671403 50230564 50230564 63423001 63423001 62198273 62452752 62452752 44987219 48671053 49604115 49604115 20314360 20314360

output:

Yes
16241165 16800326 1562643 23729328 22504600 1562643 31364606 13899073 1562643 15740990 16674052 1562643 1562644

result:

ok The answer is correct.

Test #66:

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

input:

14
17008521 17008521 17440120 44338597 44338597 42528453 45138523 45138523 43354927 34182290 34182290 33775196 33775196 32314840

output:

Yes
1308357 1308347 1347585 28246062 1347584 6362469 8559302 6775706 3580414 3580416 3206924 4667281 3206925

result:

ok The answer is correct.

Test #67:

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

input:

14
17784224 17784224 16246661 3452639 30562832 30928394 31034175 31034175 17501619 21436456 21436456 5363633 5661668 5661668

output:

Yes
8200165 6662602 265587 265589 9302320 9485101 9590882 265587 6716784 10651621 647785 647791 945826

result:

ok The answer is correct.

Test #68:

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

input:

14
69235639 69235639 68987597 68987597 57039158 57039158 55926434 63346321 63346321 66237443 66237443 64858399 62617841 60839024

output:

Yes
17611255 4302032 17363203 4302033 5414764 4302033 4302034 7628096 5120799 8213061 6834017 5713738 5120799

result:

ok The answer is correct.

Test #69:

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

input:

14
87 74 86 89 86 79 79 14 37 9 33 33 38 38

output:

No

result:

ok The answer is correct.

Test #70:

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

input:

14
8 10 24 23 23 19 31 30 15 16 2 23 34 27

output:

No

result:

ok The answer is correct.

Test #71:

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

input:

14
72 72 72 64 72 62 15 15 42 42 6 26 43 25

output:

No

result:

ok The answer is correct.

Test #72:

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

input:

14
124 125 103 108 120 120 121 127 130 130 69 43 48 48

output:

No

result:

ok The answer is correct.

Test #73:

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

input:

14
18 3 16 11 11 24 24 25 25 10 14 17 13 10

output:

No

result:

ok The answer is correct.

Test #74:

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

input:

14
1432833 514825 398091 1958543 1337446 1729822 2090128 1970313 1970313 2487044 1900924 2317778 425241 425241

output:

No

result:

ok The answer is correct.

Test #75:

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

input:

14
24 3 0 31 31 23 9 15 21 25 21 25 27 27

output:

No

result:

ok The answer is correct.

Test #76:

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

input:

14
27 46 64 56 68 68 68 13 74 74 74 51 26 55

output:

No

result:

ok The answer is correct.

Subtask #4:

score: 25
Accepted

Dependency #1:

100%
Accepted

Test #77:

score: 25
Accepted
time: 6ms
memory: 4584kb

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:

Yes
14 14 0 12 25 0 9 12 5 7 21 0 41 0 5 12 15 10 3 17 18 0 9 0 7 10 1 0 17 0 3 5 9 0 13 0 0 6 0 4 6 10 5 0 2 9 7 1

result:

ok The answer is correct.

Test #78:

score: 0
Accepted
time: 7ms
memory: 4528kb

input:

49
3 3 29 29 31 31 34 34 34 34 31 22 22 21 21 21 36 36 37 42 42 41 22 22 6 6 19 37 65 71 71 77 78 78 76 76 42 46 46 40 60 60 60 60 60 60 6 6 4

output:

Yes
3 0 29 0 31 0 34 0 11 8 3 4 3 3 3 0 10 5 7 10 9 3 4 0 6 0 2 5 13 19 9 19 20 1 44 8 9 13 0 20 40 0 60 0 57 1 3 1

result:

ok The answer is correct.

Test #79:

score: 0
Accepted
time: 7ms
memory: 4588kb

input:

49
18 18 18 16 16 59 61 64 64 57 57 78 78 78 78 81 92 92 92 92 89 81 47 64 64 63 59 65 65 63 52 52 34 34 33 8 13 13 17 17 14 16 19 19 13 13 18 18 18

output:

Yes
9 9 0 16 0 13 14 17 10 17 0 78 0 78 0 36 47 1 28 25 21 3 8 15 14 12 0 28 26 2 27 6 8 7 1 0 2 1 5 2 1 3 6 1 2 1 4 4

result:

ok The answer is correct.

Test #80:

score: 0
Accepted
time: 9ms
memory: 4604kb

input:

50
43 47 47 42 42 41 51 51 57 62 62 61 58 58 67 67 68 68 63 68 68 67 71 71 76 76 76 76 76 76 48 48 48 48 36 36 33 33 4 8 8 6 6 11 11 3 3 10 10 10

output:

Yes
10 14 5 10 9 4 27 0 19 22 21 0 58 0 67 0 68 0 21 24 23 0 71 0 76 0 76 0 76 0 48 0 48 0 36 0 33 0 2 6 0 6 0 11 0 3 0 5 5

result:

ok The answer is correct.

Test #81:

score: 0
Accepted
time: 3ms
memory: 4640kb

input:

49
12 14 14 16 16 10 18 32 32 30 30 0 0 5 5 4 0 9 9 18 18 18 30 41 43 43 39 39 35 24 26 27 27 6 6 13 13 19 22 22 21 21 44 44 43 43 33 33 31

output:

Yes
6 8 0 16 0 2 4 10 8 8 0 0 0 3 2 0 0 9 0 9 9 0 5 8 10 7 7 6 0 8 9 10 0 6 0 1 1 4 7 1 2 2 20 3 16 4 6 4

result:

ok The answer is correct.

Test #82:

score: 0
Accepted
time: 5ms
memory: 4424kb

input:

48
13 13 11 3 36 40 40 40 36 35 35 30 18 18 33 33 33 23 20 20 17 19 20 20 0 10 31 31 28 30 30 5 16 16 13 12 12 36 39 39 37 37 25 25 26 26 7 7

output:

Yes
7 5 1 0 9 11 11 9 0 20 15 0 8 1 10 10 5 1 10 1 3 4 5 0 0 5 26 0 14 16 0 1 7 4 2 5 0 18 21 0 19 4 5 5 6 1 1

result:

ok The answer is correct.

Test #83:

score: 0
Accepted
time: 6ms
memory: 4512kb

input:

49
72 72 71 33 98 98 89 89 174 174 163 163 170 170 82 98 98 202 202 179 164 282 299 299 316 316 300 262 250 250 236 154 140 148 150 150 148 148 131 95 95 106 106 108 108 81 78 78 51

output:

Yes
31 30 11 0 55 1 46 1 131 1 120 1 127 1 20 36 1 45 22 13 14 73 90 4 67 51 32 22 38 24 9 7 7 11 13 4 33 16 1 52 1 37 6 36 9 6 9 2

result:

ok The answer is correct.

Test #84:

score: 0
Accepted
time: 11ms
memory: 4612kb

input:

50
148 360 360 392 392 399 399 384 350 350 346 346 306 306 314 314 346 346 323 321 174 293 299 304 342 342 340 328 328 227 227 192 330 339 339 318 327 327 326 266 266 182 204 204 67 67 79 79 85 85

output:

Yes
18 230 14 79 77 86 75 1 302 1 298 1 258 1 266 1 97 74 73 24 4 29 30 31 45 43 37 37 12 56 21 1 134 143 2 86 91 90 2 202 2 60 82 2 3 2 7 6 13

result:

ok The answer is correct.

Test #85:

score: 0
Accepted
time: 8ms
memory: 4524kb

input:

48
200 224 224 200 267 267 259 231 246 246 215 215 196 184 180 180 270 270 270 234 230 233 233 186 114 165 165 160 190 212 212 243 243 239 239 143 143 162 162 262 264 264 246 234 238 238 22 22

output:

Yes
100 124 0 17 46 38 24 22 43 7 42 23 17 14 19 7 51 51 33 11 39 42 17 0 38 66 61 0 25 47 24 79 8 114 9 11 10 20 12 44 46 36 32 1 218 2 2

result:

ok The answer is correct.

Test #86:

score: 0
Accepted
time: 7ms
memory: 4584kb

input:

49
226 226 216 196 196 158 193 253 253 257 257 257 201 300 300 320 384 392 392 385 385 263 291 291 269 287 287 277 277 487 487 497 497 496 482 507 511 511 503 331 152 173 189 214 214 232 232 221 191

output:

Yes
49 39 3 48 10 3 14 74 12 46 46 3 10 33 29 37 69 77 8 167 45 3 150 3 33 51 8 16 15 226 12 53 52 45 39 54 58 52 20 3 4 7 11 36 9 37 26 11

result:

ok The answer is correct.

Test #87:

score: 0
Accepted
time: 7ms
memory: 4456kb

input:

49
247 247 231 383 383 381 379 398 398 397 391 195 200 227 227 197 197 339 339 337 344 344 379 388 388 379 343 405 405 412 412 402 402 412 412 398 398 415 430 430 382 382 384 384 341 198 122 124 124

output:

Yes
153 2 47 124 122 2 58 66 65 62 12 9 15 42 11 14 12 156 2 40 47 35 51 60 51 39 2 311 2 318 2 308 2 304 3 226 10 73 88 31 76 33 77 34 12 4 3 16

result:

ok The answer is correct.

Test #88:

score: 0
Accepted
time: 8ms
memory: 4488kb

input:

48
196 196 284 284 280 280 263 303 387 387 388 388 343 321 321 328 328 283 283 151 157 157 164 164 198 203 203 172 166 178 259 280 294 294 288 243 239 239 235 226 226 330 333 333 302 287 295 295

output:

Yes
58 3 146 3 142 3 22 42 126 16 91 46 35 35 3 190 3 145 3 8 14 3 26 3 20 25 7 5 5 7 24 31 41 35 20 4 48 44 3 18 13 43 46 29 24 24 32

result:

ok The answer is correct.

Test #89:

score: 0
Accepted
time: 5ms
memory: 4392kb

input:

48
244 256 256 248 253 253 269 269 250 229 229 67 252 322 261 116 372 271 372 322 333 333 393 429 429 428 347 319 294 387 234 352 370 370 317 37 193 398 10 76 215 222 222 208 344 145 171 87

output:

No

result:

ok The answer is correct.

Test #90:

score: 0
Accepted
time: 5ms
memory: 4404kb

input:

50
34 15 33 66 66 66 33 39 9 35 55 29 34 35 51 13 50 50 56 48 44 43 57 57 57 25 50 50 27 27 21 47 35 50 50 55 55 53 7 43 37 55 55 62 62 62 52 21 26 26

output:

No

result:

ok The answer is correct.

Test #91:

score: 0
Accepted
time: 5ms
memory: 4432kb

input:

49
47 64 64 64 59 74 74 3 72 19 67 71 25 61 61 58 50 49 49 58 62 70 70 69 51 70 62 62 62 62 62 54 8 41 41 41 19 40 40 20 8 24 24 20 16 16 16 19 19

output:

No

result:

ok The answer is correct.

Test #92:

score: 0
Accepted
time: 5ms
memory: 4500kb

input:

48
13 13 10 27 27 28 28 18 29 29 26 24 31 31 30 26 12 12 0 0 0 42 42 38 38 38 37 37 27 27 26 60 60 68 70 70 67 67 70 70 67 67 48 49 49 47 47 44

output:

Yes
13 0 5 22 0 19 9 0 12 9 8 0 11 10 8 1 8 0 0 0 0 17 1 7 7 1 12 1 2 1 1 20 2 15 17 2 27 2 30 2 24 5 2 9 2 6 3

result:

ok The answer is correct.

Test #93:

score: 0
Accepted
time: 6ms
memory: 4508kb

input:

50
22 22 14 24 27 27 25 25 10 47 47 45 41 42 42 44 44 43 43 0 32 32 30 27 27 10 10 14 14 14 4 11 11 9 23 23 20 28 28 22 29 31 1 28 30 30 30 30 27 27

output:

No

result:

ok The answer is correct.

Test #94:

score: 0
Accepted
time: 6ms
memory: 4488kb

input:

49
45 69 69 73 73 73 69 69 34 34 31 47 51 54 54 58 58 56 56 53 42 42 10 10 4 7 7 60 61 61 63 63 64 66 66 62 34 49 49 49 46 40 38 43 43 13 13 10 10

output:

No

result:

ok The answer is correct.

Test #95:

score: 0
Accepted
time: 6ms
memory: 4476kb

input:

48
17 17 16 16 0 27 29 32 32 36 36 39 39 35 33 21 23 23 46 46 46 46 38 38 36 36 34 34 31 33 33 36 36 30 30 28 28 23 19 19 33 37 37 15 38 39 39 0

output:

No

result:

ok The answer is correct.

Test #96:

score: 0
Accepted
time: 6ms
memory: 4472kb

input:

49
18 25 25 24 30 31 31 32 32 31 27 43 43 48 48 53 53 51 39 48 48 47 47 11 11 53 28 24 24 23 21 24 24 24 24 19 38 39 39 38 38 39 42 42 41 36 39 39 37

output:

No

result:

ok The answer is correct.

Subtask #5:

score: 17
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #97:

score: 17
Accepted
time: 5ms
memory: 4484kb

input:

49
35 35 43 43 40 52 54 54 52 52 31 11 0 11 27 27 25 25 25 29 29 25 25 23 23 17 17 17 22 22 11 6 0 24 24 36 43 43 43 39 8 8 6 6 0 21 27 27 27

output:

Yes
7 3 8 5 4 8 10 7 9 3 1 0 0 3 12 10 1 21 0 29 0 25 0 23 0 5 3 4 9 2 1 0 0 24 0 9 12 12 10 0 8 0 6 0 0 7 10 10

result:

ok The answer is correct.

Test #98:

score: 0
Accepted
time: 9ms
memory: 4656kb

input:

49
53 53 65 68 68 70 75 75 70 75 75 66 66 61 61 61 61 79 81 81 87 87 87 84 85 85 80 69 69 73 73 77 77 77 23 23 28 32 32 32 28 28 35 35 31 25 28 28 14

output:

Yes
53 0 10 13 5 10 15 10 5 22 6 12 7 0 17 11 13 22 24 0 16 16 5 12 13 10 5 9 5 7 7 9 9 0 10 1 3 5 5 2 5 2 9 5 2 2 5 1

result:

ok The answer is correct.

Test #99:

score: 0
Accepted
time: 8ms
memory: 4528kb

input:

50
3 3 28 29 29 22 22 30 32 34 34 33 39 39 35 17 29 30 30 29 29 27 27 23 23 40 40 82 82 81 81 78 80 80 80 61 61 56 68 69 69 68 50 36 13 13 7 7 14 14

output:

Yes
3 0 14 15 0 22 0 10 11 13 0 11 16 12 0 3 9 10 2 17 2 15 0 23 0 40 0 82 0 81 0 17 18 18 3 11 6 6 10 11 10 5 3 0 9 1 3 1 10

result:

ok The answer is correct.

Test #100:

score: 0
Accepted
time: 6ms
memory: 4576kb

input:

49
39 39 35 29 36 45 45 45 45 40 41 47 47 47 16 16 16 16 17 17 18 20 20 33 43 55 55 73 73 75 76 76 69 63 63 42 42 42 48 50 50 41 41 42 44 44 4 11 11

output:

Yes
10 6 3 2 4 8 6 8 5 2 7 10 10 0 16 0 16 0 17 0 9 11 0 11 16 28 0 73 0 26 27 23 0 63 0 42 0 14 17 19 0 41 0 21 23 0 2 9

result:

ok The answer is correct.

Test #101:

score: 0
Accepted
time: 8ms
memory: 4584kb

input:

48
98 101 165 185 185 516 520 550 550 390 386 645 668 668 676 676 691 691 677 658 658 521 553 553 525 464 406 476 513 513 414 414 464 501 501 492 590 590 591 591 462 462 416 200 266 278 304 304

output:

Yes
3 4 36 56 2 99 101 131 57 4 30 67 75 70 74 73 88 74 4 484 4 63 93 65 44 25 29 64 101 28 39 4 60 83 74 58 190 5 403 5 160 114 6 6 28 34 60

result:

ok The answer is correct.

Test #102:

score: 0
Accepted
time: 4ms
memory: 4640kb

input:

48
233 233 353 558 565 565 529 529 458 323 400 456 501 501 517 517 339 373 373 335 335 419 419 395 334 334 340 340 295 147 147 362 362 377 377 379 379 264 264 251 152 152 70 162 208 208 198 198

output:

Yes
187 1 52 106 113 90 93 73 1 19 34 62 107 32 155 21 21 55 18 39 17 80 56 24 27 1 134 89 15 6 9 127 23 138 24 140 24 25 22 2 85 3 2 26 72 25 63

result:

ok The answer is correct.

Test #103:

score: 0
Accepted
time: 8ms
memory: 4584kb

input:

49
842 842 917 917 927 927 929 930 930 745 745 613 576 576 560 815 815 893 907 937 937 869 883 883 883 883 848 848 729 780 780 803 803 800 800 561 561 560 629 629 627 627 585 634 634 643 655 655 388

output:

Yes
513 7 588 7 555 8 215 216 53 189 57 8 204 8 98 353 8 179 186 216 8 79 93 66 104 67 69 47 46 104 8 431 8 428 8 99 98 8 257 8 86 36 40 89 36 69 81 9

result:

ok The answer is correct.

Test #104:

score: 0
Accepted
time: 10ms
memory: 4484kb

input:

50
649 765 765 751 765 765 898 898 955 955 941 941 995 995 978 916 881 881 844 768 740 740 735 661 652 605 605 586 586 560 465 465 411 492 492 428 428 385 477 477 594 594 564 564 497 526 526 515 463 463

output:

Yes
160 276 7 211 225 7 562 7 619 7 605 7 176 159 128 24 147 110 72 28 77 72 35 32 24 25 8 124 98 8 93 8 16 97 15 34 9 8 35 15 152 15 90 23 23 43 32 15 21

result:

ok The answer is correct.

Test #105:

score: 0
Accepted
time: 10ms
memory: 4520kb

input:

50
9757021 9757021 9279087 10211787 10211787 13159399 13159399 12592915 12592915 10743184 10743184 11075654 13281929 13281929 13197920 13365343 14008687 14515635 14515635 14452939 12634082 15780207 15780207 15663442 15196550 13950446 12389587 12774326 12774326 10499331 10499331 10443669 4834240 4834...

output:

Yes
5844301 81515 1402728 1713628 1713628 4661240 81515 8680154 81516 6830423 81516 2441975 3587117 3503108 81516 1128314 1342762 1627584 1564888 945495 945498 2040168 1923403 1689957 1274589 81516 4279171 4663910 81516 3361874 3306212 81516 509815 493180 81516 277120 81516 81519 4688853 81516 28287...

result:

ok The answer is correct.

Test #106:

score: 0
Accepted
time: 8ms
memory: 4532kb

input:

49
3140091 4599712 4599712 4306933 3855850 3855850 3982474 3982474 12583623 15412358 15412358 15121551 15112361 14133071 14270248 14270248 14074890 14460929 14460929 9136003 12828613 12828613 12718829 11763511 10600063 14347165 15864793 15864793 16488871 16505450 16505450 12803475 12803475 12075780 ...

output:

Yes
65427 941627 648848 65418 81723 81685 84732 84700 706061 1586135 1295328 1290733 964303 964301 1101486 213538 2683002 3069041 213538 213542 1676821 1567037 1089378 213539 620377 2493928 4011556 225137 3762401 3778980 225137 3614269 225137 1162796 1778988 1011256 225137 618526 806977 806974 96651...

result:

ok The answer is correct.

Test #107:

score: 0
Accepted
time: 8ms
memory: 4488kb

input:

48
7860438 12158478 13753704 13771006 13771006 18767757 18927795 18968593 18968593 18560763 18649287 18649287 18224800 18224800 15243518 15243518 15175681 9471368 9471368 8990283 8990283 7894916 7633966 8802718 8802718 3876185 3876185 3822869 3822869 1212984 3582842 3582842 5846236 7012301 7012301 7...

output:

Yes
395113 1827793 2625406 2642708 395111 2234968 2314987 2355785 1037601 2730152 2818676 1037602 4086727 1037606 1105444 1037607 519029 519033 25808 4462145 3366778 25808 3236303 4405055 25808 2689017 25808 2635701 25808 25812 2395670 25808 447990 739507 739506 1088545 816557 278043 1530463 278044 ...

result:

ok The answer is correct.

Test #108:

score: 0
Accepted
time: 5ms
memory: 4520kb

input:

50
8562640 8562640 8791060 8953930 9955044 9955044 9558730 7820204 7504730 7504730 12381579 12439159 12439159 10733532 10733532 11677206 12477244 12477244 11307156 11046660 13033970 13033970 12141178 15057332 16705610 16782829 16782829 15921686 15014152 14466729 14582484 14582484 15253074 15253074 1...

output:

Yes
1726816 142413 500872 555162 1253876 857562 258158 195062 195068 195061 2633492 2691072 142413 3897708 142413 1770411 2570449 1585386 142413 1498554 2938605 2045813 142413 1760391 2440471 2517690 2048509 1749596 142413 3886659 4002414 142413 8417250 142413 2373938 3604167 142413 2877677 3813706 ...

result:

ok The answer is correct.

Test #109:

score: 0
Accepted
time: 5ms
memory: 4352kb

input:

50
16 26 54 22 22 25 25 37 37 37 36 36 34 35 35 51 6 11 9 36 12 12 23 3 49 49 48 23 47 47 11 11 18 7 44 44 5 44 44 18 5 52 57 20 57 48 52 53 0 0

output:

No

result:

ok The answer is correct.

Test #110:

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

input:

48
10 30 28 54 46 32 14 14 16 16 25 25 58 40 40 37 55 20 63 59 61 61 53 53 53 50 50 42 42 21 21 36 24 16 36 19 60 28 30 30 22 36 35 12 31 31 26 23

output:

No

result:

ok The answer is correct.

Test #111:

score: 0
Accepted
time: 5ms
memory: 4400kb

input:

48
5092766 5227138 5227138 5238104 7971031 7971031 7903225 7197892 7197892 6605419 2479643 2479643 9424971 9554015 9554015 10267184 13617473 9605729 10316478 10316478 14221231 2075244 7396399 15160740 15505829 15505829 15796933 6369046 1709256 14327010 14327010 14114028 5147104 9312032 9312032 15981...

output:

No

result:

ok The answer is correct.

Test #112:

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

input:

49
8884683 8884683 9151162 9151162 7571437 7571437 10077005 10077005 11445047 11445047 11861700 11861700 11795572 10927878 2505781 2855773 4458081 4458081 4106198 3325132 6504551 6504551 9625607 7059089 8322561 8322561 7631437 6776593 7507105 7507105 7015845 3624049 5711859 5711859 5688065 5688065 5...

output:

No

result:

ok The answer is correct.

Test #113:

score: 0
Accepted
time: 5ms
memory: 4452kb

input:

48
16 24 24 26 26 26 32 32 30 26 26 32 34 34 29 29 26 30 30 20 5 5 27 39 39 76 39 59 67 67 66 66 77 80 80 79 79 75 65 77 77 85 85 85 85 65 0 0

output:

No

result:

ok The answer is correct.

Test #114:

score: 0
Accepted
time: 5ms
memory: 4548kb

input:

50
7744445 8225578 8900877 8900877 13083017 13083017 12156080 12945934 12945934 14277370 14331387 14331387 12887705 12887705 12977812 12977812 9845822 7720338 7720338 7506879 7506879 9795777 9795777 8982663 8492451 8864389 9088182 9088182 10244216 10444212 10809269 10809269 6897821 11852797 11852797...

output:

No

result:

ok The answer is correct.

Test #115:

score: 0
Accepted
time: 6ms
memory: 4464kb

input:

48
37 42 42 71 71 71 74 74 78 78 83 83 86 86 90 90 92 92 81 81 81 81 81 63 70 70 72 72 7 64 63 63 58 58 55 69 69 66 66 63 61 62 62 55 55 55 47 47

output:

No

result:

ok The answer is correct.

Test #116:

score: 0
Accepted
time: 7ms
memory: 4540kb

input:

48
51 13 13 8 8 35 35 33 27 34 34 34 31 31 34 53 53 52 52 52 34 34 58 62 62 60 60 57 57 56 40 43 43 17 17 17 17 17 17 14 17 17 15 25 28 28 28 28

output:

No

result:

ok The answer is correct.

Subtask #6:

score: 0
Runtime Error

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #117:

score: 0
Runtime Error

input:

79
19 19 22 22 53 54 54 51 42 42 42 46 54 56 56 57 57 0 60 60 57 58 58 60 60 43 36 44 46 46 36 51 62 62 73 73 73 73 66 66 78 78 75 75 70 70 72 72 71 66 66 64 76 76 76 70 70 66 53 53 61 61 62 63 63 64 74 74 72 74 74 6 13 13 6 0 7 7 0

output:


result: