QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#496405#9133. Function with Many Maximumsucup-team1231#AC ✓21ms10060kbC++141.2kb2024-07-28 08:55:132024-07-28 08:55:13

Judging History

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

  • [2024-07-28 08:55:13]
  • 评测
  • 测评结果:AC
  • 用时:21ms
  • 内存:10060kb
  • [2024-07-28 08:55:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int LLI;

LLI a[500000];
LLI suff[500000];
int main() {
    int i,b;
    cin >> b;
    b = 100000;

    int k,n = 3*b-1;
    a[1] = 5e10;
    for (k = 1; k < 2*b-1; k += 2) {
        double l = (double) (n-k+3)/(n-k-1)*a[k];
        double r = (k == 2*b-1-2) ? 1e99:((double) (n-k+2)/(n-k-2)*a[k]);
        //if((k % 1000)==1)cout<<fixed<<setprecision(20)<<l<<","<<r<<endl;
        LLI x = floor(l)+1;
        if ((l < x) && (x < r)) {
            a[k+2] = x;
            a[k+1] = (n-k-1)*a[k+2]-(n-k+2)*a[k];
            assert(a[k] < a[k+1]);
            assert(a[k+1] < a[k+2]);
        }
        else assert(0);
    }
    for (k = 2*b; k <= n; k++) a[k] = a[k-1]+1;
    assert(a[n] < 1e12);

    for (k = n; k >= 1; k--) suff[k] = suff[k+1]+a[k];
    for (k = 1; k <= n; k++) {
        //cout << suff[k]+(n-k+1)*a[k] << " ";
        assert(suff[k]+(n-k+1)*a[k] <= suff[1]+(n-1+1)*a[1]);
        if ((k & 1) && (k <= 2*b-1)) assert(suff[k]+(n-k+1)*a[k] == suff[1]+(n-1+1)*a[1]);
    }
    //cout << endl;

    //cout<<a[n]<<endl;
    //return 0;
    printf("%d\n",n);
    for (i = 1; i <= n; i++) printf("%lld%c",a[i],(i == n) ? '\n':' ');

    return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 21ms
memory: 10060kb

input:

4

output:

299999
50000000000 50000199978 50000666674 50000766543 50001333361 50001633010 50002000062 50002199388 50002666776 50002765675 50003333503 50003631858 50004000244 50004197958 50004666998 50004763967 50005333765 50005629866 50006000546 50006195688 50006667340 50006761419 50007334147 50007627034 50008...

result:

ok n=299999, max_a=449982318075, max_num=100000 >= 4

Test #2:

score: 0
Accepted
time: 18ms
memory: 8608kb

input:

100000

output:

299999
50000000000 50000199978 50000666674 50000766543 50001333361 50001633010 50002000062 50002199388 50002666776 50002765675 50003333503 50003631858 50004000244 50004197958 50004666998 50004763967 50005333765 50005629866 50006000546 50006195688 50006667340 50006761419 50007334147 50007627034 50008...

result:

ok n=299999, max_a=449982318075, max_num=100000 >= 100000

Extra Test:

score: 0
Extra Test Passed