Submission #43638

#	Time	Username	Problem	Language	Result	Execution time	Memory
43638		spencercompton	Gap (APIO16_gap)	C++14	100 / 100	74 ms	3580 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
// int cnt;
// vector<long long> li;
// void MinMax(long long a, long long b, long long *c, long long *d){
//     cnt++;
//     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;
    vector<long long> all;
    long long ans = 0LL;
    if(T==1){
        int maxim = (N+1)/2;
        long long l = 1LL;
        long long r = maxval;
        for(int i = 0; i<maxim; i++){
            MinMax(l,r,&mn,&mx);
            all.push_back(mn);
            all.push_back(mx);
            l = mn+1;
            r = mx-1;
        }
        sort(all.begin(),all.end());
    }
    else{
        MinMax(1,maxval,&mn,&mx);
        long long s = mn;
        long long e = mx;
        if(N==1){
            return e-s;
        }
        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;
        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(){
//     cnt = 0;
//     li.push_back(2);
//     li.push_back(3);
//     li.push_back(6);
//     li.push_back(8);
//     cout << findGap(1,4) << endl;
//     cout << cnt << endl;
// }

Compilation message (stderr)

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

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