Submission #125941

#	Time	Username	Problem	Language	Result	Execution time	Memory
125941		kjp4155	Gap (APIO16_gap)	C++17	89.12 / 100	77 ms	3304 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
ll MX = 1e18;
ll A[500500];
 
ll findGap1(int N){
    int L=1, R=N;
    ll mn = 0, mx = MX;
    while( L <= R ){
        ll a,b;
        MinMax(mn, mx, &a, &b);
        A[L++] = a; A[R--] = b;
        mn = a + 1; mx = b-1;
    }
 
    ll ans = 0;
    for(int i=1;i<N;i++) ans = max(ans, A[i+1]-A[i]);
 
    return ans;
}
 
ll findGap2(int N){
    ll L = 0, R = 1e18;
    MinMax(L, R, &L, &R);

    if( N == 2 ){
        return R-L;
    }

    ll gap = (R-L+(N-1))/(N-2);
    ll ans = 0;

    vector<ll> v;
    v.push_back(L);
    for(ll i=L;i<R;i+=gap){
        ll l,r; MinMax(i, i+gap, &l, &r);
        if( l != -1 ) v.push_back(l);
        if( r != -1 ) v.push_back(r);
    }

    v.push_back(R);
    for(int i=0;i<v.size()-1;i++) ans = max(ans, v[i+1]-v[i]);

    return ans;
}
 
long long findGap(int T, int N){
    if( T == 1 ) return findGap1(N);
    else return findGap2(N);
}

Compilation message (stderr)

gap.cpp: In function 'll findGap2(int)':
gap.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size()-1;i++) ans = max(ans, v[i+1]-v[i]);
                 ~^~~~~~~~~~~

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