QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#496405 | #9133. Function with Many Maximums | ucup-team1231# | AC ✓ | 21ms | 10060kb | C++14 | 1.2kb | 2024-07-28 08:55:13 | 2024-07-28 08:55:13 |
Judging History
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