Submission #113984

#	Time	Username	Problem	Language	Result	Execution time	Memory
113984		patrikpavic2	Gap (APIO16_gap)	C++17	100 / 100	58 ms	4208 KiB

gap

#include "gap.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>

typedef long long ll;

using namespace std;

const ll MX = 1000000000000000000LL;

long long findGap(int T, int N){
    if(T == 2){
        ll mi, mx; MinMax(0, MX, &mi, &mx);
        ll L, R, len = mx - mi + 1;
        ll blok = len / N;
        ll lst = mi, ans = blok;
        for(ll i = mi + 1;i < mx;){
            MinMax(i, i + ans - 1, &L, &R); i += ans;
            if(L != -1){
                ans = max(ans, L - lst);
                lst = R;
            }
        }
        ans = max(ans, mx - lst);
        return ans;
    }
    else{
        ll L = 0, R = MX;
        vector < ll > V;
        while(V.size() != N){
            ll nw1, nw2;
            MinMax(L, R, &nw1, &nw2);
            V.push_back(nw1);
            if(nw1 != nw2)
                V.push_back(nw2);
            L = nw1 + 1, R = nw2 - 1;
        }
        sort(V.begin(), V.end());
        ll ans = 0;
        for(int i = 1;i < V.size();i++)
            ans = max(ans, V[i] - V[i - 1]);
        return ans;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:32:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(V.size() != N){
               ~~~~~~~~~^~~~
gap.cpp:42:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1;i < V.size();i++)
                       ~~^~~~~~~~~~

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