QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#414932	#2929. Concert Rehearsal	TheSleepyDevil	WA	3ms	15644kb	C++17	6.6kb	2024-05-20 03:23:10	2024-05-20 03:23:10

Judging History

你现在查看的是最新测评结果

[2024-05-20 03:23:10]
评测

测评结果：WA
用时：3ms
内存：15644kb

查看

[2024-05-20 03:23:10]
提交

answer

    /*
     Hell, 'til I reach Hell, I ain't scared
     Mama checkin' in my bedroom, I ain't there
                                                */
    #include<bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    using namespace std;

    #define Major  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define TxtIO   freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    #define read(a,n) for(int i = 0 ; i<n ; i++) cin>>a[i];
    #define write(a) for(auto x : a) cout<<x<<" ";
    #define int long long
    #define pb push_back
    #define all(a)  a.begin(),a.end()
    #define el "\n"

    typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

    const int inf=4e18;

    int dx[]={1,0,-1,0,1,1,-1,-1};
    int dy[]={0,1,0,-1,1,-1,1,-1};

    const int mod=1e9+7;
    const int MAX =1e6+7;

   // ---------------------------Function----------------------------------//
    int n,p,k;
     vector<array<int,2>>arr;
     vector<int>pre;
     int check(int st,int kam){
        int sum=0;
        int cnt=kam/n,lft=kam%n;
        sum+=cnt*pre[n-1];
        if((st+lft-1<=0))return sum;
        sum+=pre[min(n-1,st+lft-1)]-(!st?0:pre[st-1]);

         int mnfo2=0;
         if((st+lft-1)>=n){
            mnfo2=n-(st+lft-1);
             sum+=pre[mnfo2];
         }
//        cout<<sum<<" "<<mnfo2<<el;
//        cout<<mnfo2<<el;


        return sum;
     }
     int vis[MAX],ans[MAX],base[MAX];
    void TestCake(){
        cin>>n>>p>>k;

        int sum=0;
        for(int i=0;i<n;i++){
            int x;cin>>x;
            arr.pb({x,i});sum+=x;
            pre.pb(sum);
        }
        vector<array<int,2>>nxt;
        for(int i=0;i<n;i++){
            int l=1,r=1e9,z=1;
            while(l<=r){
                int mid=(l+r)/2;
                if(check(i,mid)>p){
                    z=mid;
                    r=mid-1;
                }
                else{
                    l=mid+1;
                }

            }
//        cout<<check(i,r)<<" "<<i<<" "<<r<<el;

           nxt.pb({(i+r)%n,r});
//           cout<<i<<" "<<(i+r)%n<<" "<<r<<el;
        }
        memset(vis,-1,sizeof vis);
        int st=0,cnt=0;
        vector<array<int,3>>here;
        while(vis[st]==-1){
            vis[st]=cnt;
            here.pb({st,nxt[st][0],nxt[st][1]});
            st=nxt[st][0];
            cnt++;
        }
         here.pb({st,nxt[st][0],nxt[st][1]});
//        cout<<cnt<<el;
//          for(auto x : here){
//             cout<<x[0]<<" "<<x[1]<<" "<<x[2]<<el;
//           }
        if(cnt>=k){
            for(int i=0;i<here.size()-1&&k--;i++){
                 int l=here[i][0],r=here[i][1];
//                 cout<<l<<" "<<r<<el;
                 int m3aya=here[i][2]/n,zyada=here[i][2]%n;
                 ans[0]+=m3aya;
                 ans[n]-=m3aya;
                 if(!zyada)continue;
                 r=(l+zyada-1);
                 r+=n;r%=n;

                 ans[l]++;
                 if(r>=l){
                    ans[r+1]--;
                 }
                 else{
                    ans[n]--;
                    ans[0]++;
                    ans[r+1]--;
                 }
            }

        }
        else{
            k-=cnt;

//            cout<<k<<" "<<cnt<<el;
            int id=0;
            for(int i=0;i<here.size();i++){
                if(here[i]==here.back()){id=i;break;}
            }
            for(int i=id;i<here.size()-1;i++){
                 int l=here[i][0],r=here[i][1];
//                 cout<<l<<" "<<r<<el;
                 int m3aya=(here[i][2]/n),zyada=(here[i][2]%n);
            
                 ans[0]+=m3aya;
                 ans[n]-=m3aya;
                 if(!zyada)continue;
                 r=(l+zyada-1);
                 r+=n;r%=n;
//                 cout<<m3aya<<" "<<zyada<<" "<<l<<" "<<r<<el;
                 ans[l]++;
                 if(r>=l){
                    ans[r+1]--;
                 }
                 else{
                    ans[n]--;
                    ans[0]++;
                    ans[r+1]--;
                 }
                 //

            }
            for(int z=1;z<n;z++)ans[z]+=ans[z-1];
            int sz=(cnt-id);
            int have=(k/sz),bzboz=(k%sz);
            for(int i=0;i<n;i++){
//                cout<<ans[i]<<" "<<have<<el;
                ans[i]+=(ans[i]*(have));

            }

            //base
            for(int i=0;i<id;i++){
                 int l=here[i][0],r=here[i][1];
//                 cout<<l<<" "<<r<<el;
                 int m3aya=here[i][2]/n,zyada=here[i][2]%n;
                 base[0]+=m3aya;
                 base[n]-=m3aya;
                  if(!zyada)continue;
                  r=(l+zyada-1);
                 r+=n;r%=n;

                 base[l]++;
                 if(r>=l){
                    ans[r+1]--;
                 }
                 else{
                    base[n]--;
                    base[0]++;
                    base[r+1]--;
                 }
            }
            //
           for(int i=id;i<here.size()-1&&bzboz--;i++){
                 int l=here[i][0],r=here[i][1];
//                 cout<<l<<" "<<r<<el;
                 int m3aya=here[i][2]/n,zyada=here[i][2]%n;
                 base[0]+=m3aya;
                 base[n]-=m3aya;
                  if(!zyada)continue;
                  r=(l+zyada-1);
                 r+=n;r%=n;

                 base[l]++;
                 if(r>=l){
                    base[r+1]--;
                 }
                 else{
                    base[n]--;
                    base[0]++;
                    base[r+1]--;
                 }
            }
            int mn=inf;
            for(int i=1;i<n;i++)base[i]+=base[i-1];
            for(int i=0;i<n;i++){
                ans[i]+=base[i];
               mn=min(mn,ans[i]);
            }
            cout<<mn<<el;return;
        }

            int mn=ans[0];
//          cout<<ans[0]<<" ";
            for(int z=1;z<n;z++){
                ans[z]+=ans[z-1];
//                cout<<ans[z]<<" ";
                mn=min(mn,ans[z]);
            }
            cout<<mn<<el;
    }
    //------------------------------Main---------------------------//
    signed main(){
        Major
        int T = 1;
//        cin >> T;
        while(T--){
            TestCake();
        //       cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
        }
        return 0;
    }

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 15060kb

input:

output:

result:

ok single line: '10'

Test #2:

score: 0

Accepted

time: 2ms

memory: 13164kb

input:

output:

result:

ok single line: '0'

Test #3:

score: 0

Accepted

time: 2ms

memory: 11860kb

input:

output:

result:

ok single line: '1'

Test #4:

score: 0

Accepted

time: 0ms

memory: 14764kb

input:

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 2ms

memory: 15644kb

input:

1 3 7
2

output:

result:

ok single line: '7'

Test #6:

score: 0

Accepted

time: 1ms

memory: 14420kb

input:

1 1000000000 1000000000
1

output:

1000000000000000000

result:

ok single line: '1000000000000000000'

Test #7:

score: 0

Accepted

time: 1ms

memory: 14516kb

input:

5 999999999 999999999
2
1
4
7
3

output:

58823528941176471

result:

ok single line: '58823528941176471'

Test #8:

score: 0

Accepted

time: 2ms

memory: 13640kb

input:

output:

result:

ok single line: '400'

Test #9:

score: -100

Wrong Answer

time: 3ms

memory: 15044kb

input:

980 991 978
2
1
2
1
2
3
1
1
1
3
3
3
2
2
2
2
3
3
1
3
1
2
2
3
1
2
3
3
2
3
1
2
2
3
1
3
1
3
2
2
2
1
1
2
3
3
1
2
1
1
1
2
2
2
3
3
2
1
3
3
1
3
3
1
1
2
1
1
1
1
2
1
2
3
2
1
1
3
3
2
2
1
3
3
3
2
2
3
1
2
3
3
2
2
3
2
3
2
2
2
1
3
3
1
1
3
1
2
2
2
2
1
2
2
1
1
3
2
1
1
3
1
2
3
3
3
3
3
2
2
2
3
3
1
1
2
1
3
3
3
2
2
2
3
...

output:

result:

wrong answer 1st lines differ - expected: '492', found: '489'