QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#324961#8225. 最小值之和jrjyy0 1ms3836kbC++173.6kb2024-02-11 02:23:052024-02-11 02:23:06

Judging History

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

  • [2024-02-11 02:23:06]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3836kb
  • [2024-02-11 02:23:05]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1e9;

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    --n;

    std::vector<int> s(n + 1);
    for (int i = 0; i <= n; ++i) {
        std::cin >> s[i];
    }

    std::vector f(n, std::vector(n + 1, std::vector<int>{}));
    std::vector g(n, std::vector(n + 1, std::vector<std::tuple<int, int, int>>{}));
    for (int i = 0; i < n; ++i) {
        f[i][i + 1] = {s[i] == s[i + 1] ? s[i] : -inf};
        g[i][i + 1] = {{i, -1, -1}};
    }
    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len;
            f[l][r].assign(r - l, -inf);
            g[l][r].assign(r - l, {-1, -1, -1});
            for (int i = l; i < r; ++i) {
                auto add = [&](int v, int a, int b) {
                    int c = v % (r - l);
                    if (f[l][r][c] < v) {
                        f[l][r][c] = v;
                        g[l][r][c] = {i, a, b};
                    }
                };
                int p = i - l, q = r - (i + 1);
                if (!p) {
                    int v = s[l];
                    if (v <= f[i + 1][r][v % q]) {
                        add(v, -1, v % q);
                    }
                } else if (!q) {
                    int v = s[r];
                    if (v <= f[l][i][v % p]) {
                        add(v, v % p, -1);
                    }
                } else {
                    int x, y, gcd = exgcd(p, q, x, y), lcm = p / gcd * q;
                    for (int a = 0; a < p; ++a) {
                        for (int b = 0; b < q; ++b) {
                            if (f[l][i][a] == -inf || f[i + 1][r][b] == -inf || (a - b) % gcd) {
                                continue;
                            }
                            int t = ((a - b) / gcd * x % q * p + a) % lcm;
                            if (t < 0) {
                                t += lcm;
                            }
                            int mn = std::min(f[l][i][a], f[i + 1][r][b]);
                            if (t <= mn) {
                                t = (mn - t) / lcm * lcm + t;
                                for (int o = 0; o < r - l; ++o) {
                                    int x = t - o * lcm;
                                    if (x < 0) {
                                        break;
                                    }
                                    add(x, a, b);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    auto print = [&](auto self, int l, int r, int c, int x, int d) {
        if (l == r) {
            return;
        }
        auto [i, a, b] = g[l][r][c];
        int v = (f[l][r][c] - x) / (r - l) + d;
        // std::cerr << i << ": " << "f[" << l << "][" << r << "][" << c << "] : " << v << " " << f[l][r][c] << "\n";
        assert(f[l][r][c] >= x);
        self(self, l, i, a, f[l][r][c], v);
        std::cout << v << " ";
        self(self, i + 1, r, b, f[l][r][c], v);
    };
    for (int i = 0; i < n; ++i) {
        if (f[0][n][i] != -inf) {
            std::cout << "Yes\n";
            print(print, 0, n, i, 0, 0);
            return 0;
        }
    }

    std::cout << "No\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 0ms
memory: 3836kb

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: 0ms
memory: 3836kb

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: 0ms
memory: 3504kb

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

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: 0ms
memory: 3612kb

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: 0ms
memory: 3604kb

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

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

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

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: 0ms
memory: 3548kb

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: 0ms
memory: 3548kb

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: 0ms
memory: 3536kb

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

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: 1ms
memory: 3756kb

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

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

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

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

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

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

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

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

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

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

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

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

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

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: 0ms
memory: 3756kb

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

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

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

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

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

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

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

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

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

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

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

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

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

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

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

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

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

input:

2
2 2

output:

Yes
2 

result:

ok The answer is correct.

Test #33:

score: -11
Wrong Answer
time: 0ms
memory: 3580kb

input:

1
0

output:

No

result:

wrong answer Line 1 expected P

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%