QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#500085 | #9133. Function with Many Maximums | triple___a | AC ✓ | 16ms | 9056kb | C++20 | 1.2kb | 2024-07-31 22:13:39 | 2024-07-31 22:13:40 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000007;
const int mod=998244353;
int solve(vector<int>&lst,int a,int m){
assert(m>2);
int mxw=(2*a+m-2)/(m-1);
int rem=(m+2)*a%(m-2);
rem=m-2-rem;
assert(rem<=mxw);
lst.push_back(a+rem), lst.push_back(((m+2)*a+rem)/(m-2));
assert(rem>0);
assert(a+rem<((m+2)*a+rem)/(m-2));
return ((m+2)*a+rem)/(m-2);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int x=5e10, m=300001;
vector<int> lst;
lst.push_back(x);
while (m>100000) x=solve(lst,x,m), m-=2;
while (m>1) x++, lst.push_back(x), m--;
cout<<lst.size()<<" ";
for (auto c:lst) cout<<c<<" ";
// reverse(lst.begin(), lst.end());
// // for (int i=1;i<lst.size();++i) assert(lst[i-1]<lst[i]);
// vector<int> ans;
// int sum=0,k=1,mx=0;
// for (auto c:lst) sum+=c, mx=max(mx,k*c+sum), k++;
// int cnt=0;
// sum=0, k=1;
// for (auto c:lst) {
// sum+=c;
// if (k*c+sum==mx) cerr<<k<<endl, cnt++;
// k++;
// }
// cerr<<lst.size()<<" "<<cnt;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 16ms
memory: 7960kb
input:
4
output:
300001 50000000000 50000033331 50000666669 50000899944 50001333352 50001466464 50002000048 50002032893 50002666757 50002899222 50003333480 50003465464 50004000216 50004031615 50004666965 50004897660 50005333728 50005463624 50006000504 50006029497 50006667293 50006895258 50007334096 50007460944 50008...
result:
ok n=300001, max_a=450006317163, max_num=100002 >= 4
Test #2:
score: 0
Accepted
time: 11ms
memory: 9056kb
input:
100000
output:
300001 50000000000 50000033331 50000666669 50000899944 50001333352 50001466464 50002000048 50002032893 50002666757 50002899222 50003333480 50003465464 50004000216 50004031615 50004666965 50004897660 50005333728 50005463624 50006000504 50006029497 50006667293 50006895258 50007334096 50007460944 50008...
result:
ok n=300001, max_a=450006317163, max_num=100002 >= 100000
Extra Test:
score: 0
Extra Test Passed