QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#494298 | #9133. Function with Many Maximums | ucup-team1004# | AC ✓ | 41ms | 8668kb | C++14 | 852b | 2024-07-27 15:06:00 | 2024-07-27 15:06:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans=0;
vector<ll> v;
void solve(int n,ll R)
{
ans++;
if(ans==1e5) return;
if(R==0) return;
ll l=1,r=R-1,mid;
while(l<r)
{
mid=(l+r)>>1;
if(R*n<=mid*(n+4)) r=mid;
else l=mid+1;
}
l--;
v.push_back(l);
v.push_back(R*n-l*(n+3));
solve(n+2,l);
}
bool chk()
{
sort(v.begin(),v.end());
for(int i=0;i<(int)v.size()-1;i++)
if(v[i]==v[i+1]) return 0;
ll ans=0,cnt=0,sum=0;
for(ll x:v) sum+=x;
for(int i=0;i<(int)v.size();i++)
{
ll res=sum+((int)v.size()-i)*v[i];
if(res>ans) ans=res,cnt=1;
else if(res==ans) cnt++;
sum-=v[i];
}
return cnt==1e5;
}
int main()
{
int n=3e5;
ll inf=1e12;
for(int i=1;i<=n;i++) v.push_back(inf-i);
solve(n,inf-n);
printf("%d\n",(int)v.size());
for(ll x:v) printf("%lld ",x);
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 41ms
memory: 8668kb
input:
4
output:
499998 999999999999 999999999998 999999999997 999999999996 999999999995 999999999994 999999999993 999999999992 999999999991 999999999990 999999999989 999999999988 999999999987 999999999986 999999999985 999999999984 999999999983 999999999982 999999999981 999999999980 999999999979 999999999978 9999999...
result:
ok n=499998, max_a=999999999999, max_num=100000 >= 4
Test #2:
score: 0
Accepted
time: 36ms
memory: 8068kb
input:
100000
output:
499998 999999999999 999999999998 999999999997 999999999996 999999999995 999999999994 999999999993 999999999992 999999999991 999999999990 999999999989 999999999988 999999999987 999999999986 999999999985 999999999984 999999999983 999999999982 999999999981 999999999980 999999999979 999999999978 9999999...
result:
ok n=499998, max_a=999999999999, max_num=100000 >= 100000
Extra Test:
score: 0
Extra Test Passed