QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#494186#9133. Function with Many Maximumsucup-team004#AC ✓22ms10880kbC++201.6kb2024-07-27 14:37:362024-07-27 14:37:36

Judging History

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

  • [2024-07-27 14:37:36]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:10880kb
  • [2024-07-27 14:37:36]
  • 提交

answer

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    constexpr int B = 100000;
    int b;
    std::cin >> b;
    assert(b <= B);
    
    i64 sum = 0;
    
    constexpr int N = 5 * B;
    constexpr int T = 1000;
    std::vector<i64> a(N);
    for (int i = 0; i < N; i++) {
        if (8E22 / (i + 1) / (i + 2) > 1E12 - i) {
            a[i] = 1E12 - i;
        } else {
            a[i] = 8E22 / (i + 1) / (i + 2);
        }
    }
    
    std::vector<i64> f(N);
    sum = 0;
    for (int i = 0; i < N; i++) {
        f[i] = (i + 2) * a[i] + sum;
        if (i >= N - 2 * B && f[i] - f[i - 1] < 0) {
            i64 t = f[i - 1] - f[i];
            a[i] += t / (i + 2) + 1;
            f[i] = (i + 2) * a[i] + sum;
        }
        sum += a[i];
    }
    for (int i = 1; i < N; i++) {
        assert(a[i] < a[i - 1]);
    }
    for (int i = N - 2; i >= N - 2 * B; i -= 2) {
        if (a[i] - (f[i + 1] - f[i - 1]) > a[i + 1]) {
            a[i] -= (f[i + 1] - f[i - 1]);
        } else {
            assert(false);
        }
    }
    for (int i = N - 2 * B - 1; i >= 0; i--) {
        a[i] = a[i + 1] + 1;
    }
    sum = 0;
    for (int i = 0; i < N; i++) {
        f[i] = (i + 2) * a[i] + sum;
        sum += a[i];
    }
    for (int i = 1; i < N; i++) {
        assert(a[i] < a[i - 1]);
    }
    
    std::cout << N << "\n";
    for (int i = 0; i < N; i++) {
        std::cout << a[i] << " \n"[i == N - 1];
    }
    
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 20ms
memory: 10848kb

input:

4

output:

500000
888879977214 888879977213 888879977212 888879977211 888879977210 888879977209 888879977208 888879977207 888879977206 888879977205 888879977204 888879977203 888879977202 888879977201 888879977200 888879977199 888879977198 888879977197 888879977196 888879977195 888879977194 888879977193 8888799...

result:

ok n=500000, max_a=888879977214, max_num=100000 >= 4

Test #2:

score: 0
Accepted
time: 22ms
memory: 10880kb

input:

100000

output:

500000
888879977214 888879977213 888879977212 888879977211 888879977210 888879977209 888879977208 888879977207 888879977206 888879977205 888879977204 888879977203 888879977202 888879977201 888879977200 888879977199 888879977198 888879977197 888879977196 888879977195 888879977194 888879977193 8888799...

result:

ok n=500000, max_a=888879977214, max_num=100000 >= 100000

Extra Test:

score: 0
Extra Test Passed