QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#494946 | #9133. Function with Many Maximums | ucup-team052# | AC ✓ | 21ms | 14296kb | C++23 | 1.2kb | 2024-07-27 17:46:59 | 2024-07-27 17:47:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int mul(int x,int y) {return 1ULL*x*y%mod;}
#define int long long
#define N 500005
int a[N],sum[N],val[N],n;
const int M=1000000000000;
void push(int v)
{
a[++n]=v;
sum[n]=sum[n-1]+v;
val[n]=sum[n]+v*n;
// printf("%lld : %lld\n",n,a[n]);
// printf("%lld : %lld\n",n,val[n]);
}
signed main()
{
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
for(int i=1;i<=50000;i++)
{
push(M-i+1);
}
int V=val[n];
for(int i=1;i<=100000;i++)
{
int ok=0,tv=V-sum[n];
for(int j=1;j<=10;j++)
{
int rs=tv%(n+j+1);
int cv=tv/(n+j+1);
int diff=cv*(j-1)+j*(j-1)/2-rs;
int gov=(n+j+1+diff)/(n+j+2);
rs+=(n+j+1)*gov;
cv-=gov;
if(rs>a[n]*(j-1)-j*(j-1)) continue;
// j-1 numbers, sum = rs
// add cv
// printf("%d\n",j);
assert(j<=2);
if(j>=2) push(rs);
push(cv);
ok=1;
break;
/*
while(cv*(j-1)+j*(j-1)/2<rs)
{
rs+=n+j+1,cv--;
}
*/
}
assert(ok);
// if(!ok) cout<<"bad "<<i<<endl;
}
cout<<n<<endl;
for(int i=1;i<=n;i++) printf("%lld%c",a[i]," \n"[i==n]);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 21ms
memory: 14040kb
input:
4
output:
249997 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=249997, max_a=1000000000000, max_num=100001 >= 4
Test #2:
score: 0
Accepted
time: 16ms
memory: 14296kb
input:
100000
output:
249997 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=249997, max_a=1000000000000, max_num=100001 >= 100000
Extra Test:
score: 0
Extra Test Passed