QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#407104#8225. 最小值之和juicy_name11 5ms10308kbC++144.4kb2024-05-07 23:02:052024-05-07 23:02:08

Judging History

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

  • [2024-05-07 23:02:08]
  • 评测
  • 测评结果:11
  • 用时:5ms
  • 内存:10308kb
  • [2024-05-07 23:02:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n;
int f[maxn];
int p[85][85][85];
void exgcd(int a, int b, int &x, int &y){
    if(b == 0){
        x = 0; y = 1; return ;
    }
    exgcd(b, a % b, y, x); y -= a / b * x; return ;
}
int tp[6405]; int tc[85];
int tk[85];
pair<int, int> pc[85][85][85];
bool vis[85][85];
bool vs[85];
void dfs(int l, int r){
    if(vis[l][r]) return ;
    vis[l][r] = 1;
    if(l == r){
        if(f[l] == f[l + 1]) p[l][r][0] = f[l];
        return ;
    }
    int N = r - l + 1;
    for(int i = l;i <= r;i++){
        if(i == l){
            dfs(i + 1, r);
            if(p[i + 1][r][f[l] % (N - 1)] < f[l]) continue;
            p[l][r][f[l] % N] = max(p[l][r][f[l] % N], f[l]); continue;
        }
        if(i == r){
            dfs(l, i - 1);
            if(p[l][i - 1][f[r + 1] % (N - 1)] < f[r + 1]) continue;
            p[l][r][f[r + 1] % N] = max(p[l][r][f[r + 1] % N], f[r + 1]); continue;
        }
        dfs(l, i - 1); dfs(i + 1, r);
        int L = i - l; int R = r - i;
        int pg = __gcd(L, R); int pN = L * R / pg;
        int tx = 0, ty = 0; exgcd(L, R, tx, ty); int pR = R / pg;
        tx = (tx % pR + pR) % pR;
        for(int j = 0;j < pN;j++) tp[j] = -1;
        for(int j = 0;j < L;j++){
            if(p[l][i - 1][j] < 0) continue;
            for(int k = 0;k < R;k++){
                if(p[i + 1][r][k] < 0) continue;
                if(j % pg != k % pg) continue;
                int px = 1ll * (k - j) * tx % pR; px = (px + pR) % pR; 
                int pmi = min(p[l][i - 1][j], p[i + 1][r][k]);
                int pnum = L * px + j;
                if(pnum > pmi) continue;
                tp[pnum] = max(tp[pnum], pnum + (pmi - pnum) / pN * pN);
            }
        }
        for(int j = 0;j < N;j++) tc[j] = -1;
        for(int j = 0;j < pN;j++){
            if(tp[j] == -1) continue;
            tc[tp[j] % N] = max(tc[tp[j] % N], tp[j]);
        }
        for(int j = 0;j < N;j++){
            vs[j] = 0;
            // if(tc[j] >= 0) assert(tc[j] % N == j);
        }
        int x = (N - pN % N) % N;
        for(int j = 0;j < N;j++){
            if(vs[j]) continue;
            int now = j;
            do{
                if(tc[now] - pN > tc[(now + x) % N]){
                    tc[(now + x) % N] = tc[now] - pN;
                }
                vs[now] = 1; now = (now + x) % N;
            }while(now != j);
            do{
                if(tc[now] - pN > tc[(now + x) % N]){
                    tc[(now + x) % N] = tc[now] - pN;
                }
                now = (now + x) % N;
            }while(now != j);
        }
        for(int j = 0;j < N;j++){
            if(tc[j] > p[l][r][j]){
                p[l][r][j] = tc[j]; pc[l][r][j] = make_pair(tc[j], i);
            }
        }
    }
    // cerr << l << " " << r << endl << "? ";
    // for(int i = 0;i < N;i++){
        // cerr << p[l][r][i] << " ";
    // }
    // cerr << endl;
    return ;
}
int ans[maxn];
void dfsp(int l, int r, int num, int res){
    // cerr << "? " << l << " " << r << " " << num << " " << res << endl;
    if(l == r){
        ans[l] = f[l] - num + res; return ;
    }
    int N = r - l + 1;
    if(f[l] % N == num % N && p[l + 1][r][f[l] % (N - 1)] >= f[l]){
        ans[l] = (f[l] - num) / N + res; dfsp(l + 1, r, f[l], ans[l]); return ;
    }
    if(f[r + 1] % N == num % N && p[l][r - 1][f[r + 1] % (N - 1)] >= f[r + 1]){
        ans[r] = (f[r + 1] - num) / N + res; dfsp(l, r - 1, f[r + 1], ans[r]); return ;
    }
    int pos = pc[l][r][num % N].second;
    // cerr << pc[l][r][num % N].first << endl;
    ans[pos] = (pc[l][r][num % N].first - num) / N + res;
    dfsp(l, pos - 1, pc[l][r][num % N].first, ans[pos]);
    dfsp(pos + 1, r, pc[l][r][num % N].first, ans[pos]);
    return ;
}   
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> f[i];
    }
    if(n == 1){
        if(f[1] > 0){
            cout << "No" << endl; return 0;
        }
        cout << "Yes" << endl;
        cout << endl; return 0;
    }
    memset(p, -1, sizeof(p));
    dfs(1, n - 1);
    if(p[1][n - 1][0] < 0){
        cout << "No" << endl; return 0;
    }
    dfsp(1, n - 1, 0, 0);
    cout << "Yes" << '\n';
    for(int i = 1;i < n;i++){
        cout << ans[i] << " ";
    }
    cout << '\n';
    cout.flush(); return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

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

input:

5
14 14 12 13 13

output:

Yes
5 3 3 4 

result:

ok The answer is correct.

Test #2:

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

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1 

result:

ok The answer is correct.

Test #3:

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

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4 

result:

ok The answer is correct.

Test #4:

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

input:

5
11 11 10 5 5

output:

Yes
5 4 1 2 

result:

ok The answer is correct.

Test #5:

score: 11
Accepted
time: 2ms
memory: 7300kb

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1 

result:

ok The answer is correct.

Test #6:

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

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1 

result:

ok The answer is correct.

Test #7:

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

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8 

result:

ok The answer is correct.

Test #8:

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

input:

5
2 2 6 11 11

output:

Yes
2 0 3 8 

result:

ok The answer is correct.

Test #9:

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

input:

5
10 10 8 5 5

output:

Yes
5 3 1 2 

result:

ok The answer is correct.

Test #10:

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

input:

5
24 24 28 28 26

output:

Yes
6 6 9 7 

result:

ok The answer is correct.

Test #11:

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

input:

5
5 5 22 31 31

output:

Yes
2 1 10 19 

result:

ok The answer is correct.

Test #12:

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

input:

5
8 33 38 38 29

output:

Yes
2 11 16 9 

result:

ok The answer is correct.

Test #13:

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

input:

5
16 16 4 12 12

output:

Yes
13 1 1 9 

result:

ok The answer is correct.

Test #14:

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

input:

5
29 29 24 26 26

output:

Yes
11 6 6 8 

result:

ok The answer is correct.

Test #15:

score: 11
Accepted
time: 2ms
memory: 8740kb

input:

5
0 33 33 32 32

output:

Yes
0 13 10 12 

result:

ok The answer is correct.

Test #16:

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

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

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

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

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

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

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

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

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

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

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

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

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

input:

5
6 7 7 6 6

output:

Yes
2 3 1 3 

result:

ok The answer is correct.

Test #23:

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

input:

5
25 25 24 20 20

output:

Yes
8 7 5 5 

result:

ok The answer is correct.

Test #24:

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

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

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

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

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

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

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

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

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

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

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

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

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

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

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

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

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

input:

2
2 2

output:

Yes
2 

result:

ok The answer is correct.

Test #33:

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

input:

1
0

output:

Yes


result:

ok The answer is correct.

Test #34:

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

input:

1
233

output:

No

result:

ok The answer is correct.

Subtask #2:

score: 0
Memory Limit Exceeded

Dependency #1:

100%
Accepted

Test #35:

score: 15
Accepted
time: 1ms
memory: 6136kb

input:

8
16 16 8 8 9 9 6 6

output:

Yes
16 0 2 2 3 1 2 

result:

ok The answer is correct.

Test #36:

score: 15
Accepted
time: 1ms
memory: 6352kb

input:

8
16 16 9 21 21 23 23 23

output:

Yes
9 2 1 15 1 9 9 

result:

ok The answer is correct.

Test #37:

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

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: 15
Accepted
time: 1ms
memory: 6100kb

input:

8
13 13 15 15 24 24 24 10

output:

Yes
3 3 5 1 9 9 2 

result:

ok The answer is correct.

Test #39:

score: 15
Accepted
time: 1ms
memory: 7756kb

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: 15
Accepted
time: 1ms
memory: 7240kb

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

Yes
459 841 79 575 157 80 80 

result:

ok The answer is correct.

Test #41:

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

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: 15
Accepted
time: 2ms
memory: 8596kb

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: 15
Accepted
time: 1ms
memory: 7200kb

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
Memory Limit Exceeded

input:

8
4726918 12793592 12793592 6681214 13995142 22020836 22566624 22566624

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Memory Limit Exceeded

Dependency #1:

100%
Accepted

Test #77:

score: 25
Accepted
time: 4ms
memory: 9240kb

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: 25
Accepted
time: 5ms
memory: 10308kb

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 14 11 3 7 6 0 21 0 36 0 11 14 13 2 14 0 6 0 4 10 24 30 1 36 37 0 76 0 21 25 0 20 40 0 60 0 57 1 3 1 

result:

ok The answer is correct.

Test #79:

score: 0
Memory Limit Exceeded

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:


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%