QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#516312#9133. Function with Many Maximumsarnold518#AC ✓44ms7592kbC++171.3kb2024-08-12 15:55:442024-08-12 15:55:44

Judging History

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

  • [2024-08-12 15:55:44]
  • 评测
  • 测评结果:AC
  • 用时:44ms
  • 内存:7592kb
  • [2024-08-12 15:55:44]
  • 提交

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX = (int)1e5;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    const ll MX = 1'000'000'000'000LL;

    ll a[505050];
    for (int i = 1; i <= 300000; i++) {
        a[i] = MX - i + 1;
    }
    for (int i = 300000; i < 500000; i += 2) {
        ll ss = 0, ee = MX;
        while (ss < ee) {
            ll k = (ss + ee) / 2;
            if ((__int128)i * (i + 1) * a[i] < (__int128)(i + 2) * (i + 3) * k) {
                ee = k;
            }
            else {
                ss = k + 1;
            }
        }
        a[i + 2] = ss;
        a[i + 1] = i * a[i] - (i + 3) * (a[i + 2]);
    }

    // ll mx = -1, sum = 0, cnt = 0;
    // for (int i = 1; i <= 500000; i++) {
    //     sum += a[i];
    //     if (i != 1) assert(a[i - 1] > a[i]);
    //     if (mx < i * a[i] + sum) {
    //         mx = i * a[i] + sum;
    //         cnt = 1;
    //     }
    //     else if (mx == i * a[i] + sum) {
    //         cnt++;
    //     }
    // }
    // cout << mx << ' ' << cnt << '\n';
    
    cout << 500000 << '\n';
    for (int i = 1; i <= 500000; i++) {
        cout << a[i] << '\n';
    }
    cout << '\n';
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 35ms
memory: 7592kb

input:

4

output:

500000
1000000000000
999999999999
999999999998
999999999997
999999999996
999999999995
999999999994
999999999993
999999999992
999999999991
999999999990
999999999989
999999999988
999999999987
999999999986
999999999985
999999999984
999999999983
999999999982
999999999981
999999999980
999999999979
999999...

result:

ok n=500000, max_a=1000000000000, max_num=100001 >= 4

Test #2:

score: 0
Accepted
time: 44ms
memory: 7580kb

input:

100000

output:

500000
1000000000000
999999999999
999999999998
999999999997
999999999996
999999999995
999999999994
999999999993
999999999992
999999999991
999999999990
999999999989
999999999988
999999999987
999999999986
999999999985
999999999984
999999999983
999999999982
999999999981
999999999980
999999999979
999999...

result:

ok n=500000, max_a=1000000000000, max_num=100001 >= 100000

Extra Test:

score: 0
Extra Test Passed