Submission #43637

#	Time	Username	Problem	Language	Result	Execution time	Memory
43637		spencercompton	Gap (APIO16_gap)	C++14	70 / 100	94 ms	3556 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
// vector<long long> li;
// void MinMax(long long a, long long b, long long *c, long long *d){
//     vector<long long> ar;
//     for(int i = 0; i<li.size(); i++){
//         if(li[i]>=a && li[i]<=b){
//             ar.push_back(li[i]);
//         }
//     }
//     if(ar.size()==0){
//         *c = -1;
//         *d = -1;
//     }
//     else{
//         *c = ar[0];
//         *d = ar[ar.size()-1];
//     }
// }
long long findGap(int T, int N)
{
    long long maxval = 1000000000000000000LL;
    long long mn, mx;
    MinMax(1,maxval,&mn,&mx);
    long long s = mn;
    long long e = mx;
    if(N==1){
        return e-s;
    }
    long long ans = (e-s)/((long long)N-1LL)-1LL;
    if((e-s)%((long long)N-1LL)!=0){
        ans++;
    }
    long long last = s;
    long long check = ans+1LL;
    vector<long long> all;
    all.push_back(s);
    for(long long i = s+1LL; i<e; i+=check){
        long long r = min(e-1LL,i+check-1LL);
        MinMax(i,r,&mn,&mx);
        if(mn!=-1){
            all.push_back(mn);
            all.push_back(mx);
        }
    }
    all.push_back(e);
    for(int i = 1; i<all.size(); i++){
        ans = max(ans,all[i]-all[i-1]);
    }
    return ans;
}
// int main(){
//     li.push_back(2);
//     li.push_back(3);
//     li.push_back(6);
//     li.push_back(8);
//     cout << findGap(0,4) << endl;
// }

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i<all.size(); i++){
                     ^
gap.cpp:35:15: warning: unused variable 'last' [-Wunused-variable]
     long long last = s;
               ^

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