QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#495409 | #9133. Function with Many Maximums | ucup-team191# | AC ✓ | 21ms | 14392kb | C++23 | 1.0kb | 2024-07-27 20:37:48 | 2024-07-27 20:37:48 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int N=500010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
int n,m,b;
ll h[N],su[N],va[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//cin>>b;
b=1e5+1;
m=b;
n=2*b+1;
for (int i=0;i<=2*m;++i) h[i]=1e12-i;
for (int i=m+1;i<n;++i)
{
h[2*i]=h[2*(i-1)]*(2*i-1)/(2*i+3);
h[2*i-1]=h[2*(i-1)]*(2*i-1)-h[2*i]*(2*i+2);
if (h[2*i]==h[2*i-1])
{
cout<<i<<endl;
exit(0);
}
}
sort(h,h+2*n-1);
reverse(h,h+2*n-1);
for (int i=0;i<2*n-2;++i) assert(h[i]!=h[i+1]);
for (int i=0;i<2*n-1;++i) su[i+1]=su[i]+h[i];
ll ma=0;
for (int i=0;i<2*n-1;++i)
{
va[i]=su[i+1]+h[i]*(i+1);
ma=max(ma,va[i]);
}
int cma=0;
for (int i=0;i<2*n-1;++i) if (va[i]==ma) ++cma;
assert(cma>=b);
cout<<2*n-1<<en;
for (int i=0;i<2*n-1;++i) cout<<h[i]<<' ';
cout<<en;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 13780kb
input:
4
output:
400005 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=400005, max_a=1000000000000, max_num=100002 >= 4
Test #2:
score: 0
Accepted
time: 21ms
memory: 14392kb
input:
100000
output:
400005 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=400005, max_a=1000000000000, max_num=100002 >= 100000
Extra Test:
score: 0
Extra Test Passed