Submission #309467

#	Time	Username	Problem	Language	Result	Execution time	Memory
309467		cig32	Gap (APIO16_gap)	C++14	100 / 100	76 ms	2416 KiB

gap

#include "gap.h"
 
#include<bits/stdc++.h>
using namespace std;
long long findGap(int T, int N) {
    if(T==1){
        long long leftbound=0, rightbound=1e18;
        priority_queue <long long> pq;
        long long cnt=0;
        for(int i=0;i<=N/2;i++){
            long long l,r;
            if(cnt!=N){
                MinMax(leftbound,rightbound,&l,&r);
                pq.push(l);
                cnt++;
                if(l!=r){
                    pq.push(r);
                    cnt++;
                    leftbound=l+1;
                    rightbound=r-1;
                }
                else break;
            }
            else break;
        }
        long long prev=pq.top();
        pq.pop();
        long long ans=0;
        while(pq.size()!=0){
            ans=max(ans,prev-pq.top());
            prev=pq.top();
            pq.pop();
        }
        return ans;
    }
    else{
        // TODO: implementationt
        long long leftbound, rightbound;
        long long haha=1e18;
        MinMax(0, haha, &leftbound, &rightbound);
        if(N==2){
            return rightbound-leftbound;
        }
        leftbound++;
        rightbound--;
        long long range_size=ceil((rightbound-leftbound)*1.0/N);
        long long dbsic_noob=(rightbound-leftbound+1);
        long long dbsic_sofai=ceil(dbsic_noob*1.0/(range_size));
        long long arr[dbsic_sofai];
        long long running=leftbound-1;
        for(int i=0;i<dbsic_sofai;i++){
            arr[i]=range_size-1;
            if(i<(dbsic_noob/range_size)){
                arr[i]++;
            }
            //printf("%lld\n",arr[i]);
        }
        long long ans=0,ans1=0,ans2=0;
        long long prevl, prevr=-1;
        bool ok=true;
        for(int i=0;i<dbsic_sofai;i++){
            long long l,r;
            MinMax(running+1,running+arr[i],&l,&r);
            running+=arr[i];
            if(l==-1 && r==-1){
                continue;
            }
            else{
                if(ok==true){
                    ok=false;
                    ans1=l-leftbound+1;
                }
                ans2=rightbound+1-r;
                if(i!=0 && prevr!=-1 && ans<(l-prevr)){
                    ans=l-prevr;
                }
                prevl=l, prevr=r;
            }
        }
        ans1=max(ans1,ans2);
        ans=max(ans,ans1);
        return ans;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:59:19: warning: variable 'prevl' set but not used [-Wunused-but-set-variable]
   59 |         long long prevl, prevr=-1;
      |                   ^~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70