QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#495477 | #9133. Function with Many Maximums | ucup-team4504# | AC ✓ | 18ms | 7512kb | C++14 | 1.4kb | 2024-07-27 21:08:21 | 2024-07-27 21:08:21 |
Judging History
answer
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
//#define int long long
using namespace __gnu_pbds;
using namespace std;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
long long a[500010];
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
int n=500000;
int b;cin>>b;
int now=1;a[1]=300000000000ll;
for(int i=2;i<=b;i++){
int m=n-now+1;
long long cur=1ll*(m+1)*a[now],rem=(m-2)-cur%(m-2);
long long X=(a[now]-rem)/(m-2)+1;
a[now+1]=rem+X*(m-2);
a[now+2]=(cur+a[now+1])/(m-2);
assert(1ll*(m+1)*a[now]>1ll*(m-1)*a[now+1]);
assert(1ll*(m+1)*a[now]+1ll*a[now+1]==1ll*(m-2)*a[now+2]);
now+=2;
}
for(int i=now+1;i<=n;i++){
int m=n-i+1;
a[i]=a[i-1]+1;
assert(1ll*m*a[i-1]>1ll*(m-2)*a[i]);
}
cout<<n<<'\n';
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
cout<<'\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 16ms
memory: 7512kb
input:
4
output:
500000 300000000000 300000199980 300002400010 300002699814 300004800049 300005199445 300007200117 300007200118 300007200119 300007200120 300007200121 300007200122 300007200123 300007200124 300007200125 300007200126 300007200127 300007200128 300007200129 300007200130 300007200131 300007200132 3000072...
result:
ok n=500000, max_a=300007700110, max_num=4 >= 4
Test #2:
score: 0
Accepted
time: 18ms
memory: 7464kb
input:
100000
output:
500000 300000000000 300000199980 300002400010 300002699814 300004800049 300005199445 300007200117 300007698873 300009600214 300009698108 300012000339 300012197135 300014400493 300014695959 300016800676 300017194580 300019200888 300019692998 300021601129 300021691233 300024001398 300024189250 3000264...
result:
ok n=500000, max_a=833320390939, max_num=100000 >= 100000
Extra Test:
score: 0
Extra Test Passed