QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500085#9133. Function with Many Maximumstriple___aAC ✓16ms9056kbC++201.2kb2024-07-31 22:13:392024-07-31 22:13:40

Judging History

This is the latest submission verdict.

  • [2024-07-31 22:13:40]
  • Judged
  • Verdict: AC
  • Time: 16ms
  • Memory: 9056kb
  • [2024-07-31 22:13:39]
  • Submitted

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