QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#494691 | #9133. Function with Many Maximums | ucup-team266# | AC ✓ | 30ms | 8836kb | C++20 | 1.8kb | 2024-07-27 16:35:45 | 2024-07-27 16:35:46 |
Judging History
answer
//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 100010
using namespace std;
vector<ll> ans;
void solve(ll lim,ll n,ll st)
{
if(lim==0)
{
while(n>=0)
{
ans.push_back(st++);
n--;
}
return;
}
assert(n>0);
ans.push_back(st);
if((st*2)%n==0)
{
solve(lim-1,n-1,st+st*2/n);
return;
}
ll s=-st*2+n-(st+1)*2+n-1;
ll id=(-s+n-2)/(n-1);
ll x=st+1+id,cur=s+id*(n-1);
ans.push_back(st+1+cur);
// cout<<st<<" , "<<x<<": "<<cur<<": "<<-st*2+n*(ans.back()-st)-ans.back()*2+(n-1)*(x-ans.back()+1)<<"????\n";
assert(-st*2+n*(ans.back()-st)-ans.back()*2+(n-1)*(x-ans.back()+1)==0);
solve(lim-1,n-2,x+1);
return;
}
int main(){
ll n,lim,i,j;
// cin>>lim;
lim=100020,n=400000;
solve(lim,n-1,n*(n-1));
sort(ans.begin(),ans.end());
printf("%lld\n",n);
// cout<<ans.size()<<": "<<ans[0]<<" , "<<ans[ans.size()-1]<<endl;
for(i=0;i<ans.size();i++)
{
// if(ans[i]>1000000000000)
// {
// cout<<i<<endl;
// break;
// }
printf("%lld ",ans[i]);
}
puts("");
// __int128 mx=0;
// ll cnt=1;
// for(int _=0;_<ans.size();_++)
// {
// if(_%1000==0)
// {
// cout<<_<<endl;
// }
// i=ans[_];
// __int128 val=0;
// for(j=0;j<n;j++)
// {
// if(i<=ans[j])
// {
// val+=i+ans[j];
// }
// }
// if(mx<val)
// {
// mx=val;
// cnt=1;
// }
// else if(mx==val)
// {
// cnt++;
// }
// }
// cout<<cnt<<endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 22ms
memory: 8200kb
input:
4
output:
400000 159999600000 160000400000 160000799949 160002000017 160002399744 160003600058 160003999371 160005200123 160005598830 160006800212 160007198121 160008400325 160008797244 160010000462 160010396199 160011600623 160011994986 160013200808 160013593605 160014801017 160015192056 160016401250 1600167...
result:
ok n=400000, max_a=640245186182, max_num=100021 >= 4
Test #2:
score: 0
Accepted
time: 30ms
memory: 8836kb
input:
100000
output:
400000 159999600000 160000400000 160000799949 160002000017 160002399744 160003600058 160003999371 160005200123 160005598830 160006800212 160007198121 160008400325 160008797244 160010000462 160010396199 160011600623 160011994986 160013200808 160013593605 160014801017 160015192056 160016401250 1600167...
result:
ok n=400000, max_a=640245186182, max_num=100021 >= 100000
Extra Test:
score: 0
Extra Test Passed