QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#324946#8225. 最小值之和jrjyy0 0ms3616kbC++173.4kb2024-02-11 02:08:452024-02-11 02:08:46

Judging History

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

  • [2024-02-11 02:08:46]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3616kb
  • [2024-02-11 02:08:45]
  • 提交

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 + 1, std::vector(n + 1, std::vector<int>{}));
    std::vector g(n + 1, 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};
    }
    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) {
                int p = i - l, q = r - (i + 1);
                auto add = [&](int v, int a, int b) {
                    if (f[l][r][v % (r - l)] < v) {
                        f[l][r][v % (r - l)] = v;
                        g[l][r][v % (r - l)] = {i, a, b};
                    }
                };
                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;
                                    add(x, a, b);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    auto print = [&](auto self, int l, int r, int c, int x, int d) {
        if (l == r) {
            return;
        }
        if (r - l == 1) {
            std::cout << s[l] - x + d << " ";
            return;
        }
        auto [i, a, b] = g[l][r][c];
        int v = (f[l][r][c] - x) / (r - l) + d;
        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;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

5
14 14 12 13 13

output:

Yes
2 4 2 3 

result:

wrong answer Your answer is wrong.

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%