Submission #96005

#	Time	Username	Problem	Language	Result	Execution time	Memory
96005		oolimry	Gap (APIO16_gap)	C++14	100 / 100	99 ms	4460 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
long long findGap(int T, int N)
{
    if(T == 1){
        long long arr[N];
        int x = 0;
        long long a, b;
        a = 0;
        b = 1000000000000000005;
        long long mn, mx;
        while(true){
            MinMax(a,b,&mn,&mx);
            arr[x] = mn;
            arr[N-x-1] = mx;
            a = mn + 1;
            b = mx - 1;
            x++;
            if ((x >= (N+1)/2)) break;
        }
        long long mm = 0;
        for(int i = 0;i < N-1;i++){
            mm = std::max(mm,arr[i+1]-arr[i]);
        }
        return mm;
    }
    else{
        long long a, b;
        a = 0;
        b = 1000000000000000005;
        long long mn, mx;
        MinMax(a,b,&mn,&mx);
        std::vector<long long> v;
        v.push_back(mn);
        v.push_back(mx);
        long long dist = mx - mn - 2;
        long long small = dist / (N-1);
        long long big = small+1;
        a = mn + 1;
        for(int i = 0;i < N-1;i++){
            if(i < dist % (N-1)) b = a + big;
            else b = a + small;
            MinMax(a,b-1,&mn,&mx);
            //printf("%lld %lld\n",a,b-1);
            if(mn != -1){
                v.push_back(mn);
                v.push_back(mx);
            }
            a = b;
        }
        long long mm = 0;
        sort(v.begin(),v.end());
        for(int i = 0;i < v.size()-1;i++){
            mm = std::max(mm,v[i+1]-v[i]);
        }
        return mm;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < v.size()-1;i++){
                       ~~^~~~~~~~~~~~

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