Submission #163530

#	Time	Username	Problem	Language	Result	Execution time	Memory
163530		Akashi	Gap (APIO16_gap)	C++14	70 / 100	114 ms	6008 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;

const long long INF = 1e18;

set <long long> s;
long long findGap(int T, int N){
    if(T == 1){
        s.clear();
        long long L = 1, R = INF;

        while(L != -1 && R != -1 && L < R){
            long long x, y;
            MinMax(L, R, &x, &y);

            if(x != -1) s.insert(x), L = x + 1;
            else L = -1;
            if(y != -1) s.insert(y), R = y - 1;
            else R = -1;
        }
    }

    if(T == 2){
        s.clear();

        long long Min, Max;
        MinMax(1, INF, &Min, &Max);

        s.insert(Min); s.insert(Max);

        long long L = (Max - Min + 1) / N + 1, x, y;

        for(long long i = Min + 1; i < Max ; i = i + L){
            MinMax(i, min(i + L - 1, Max), &x, &y);

            if(x != -1) s.insert(x);
            if(y != -1) s.insert(y);
        }
    }

    long long Sol = 0;
    set <long long> :: iterator it = s.begin();
    set <long long> :: iterator it2 = next(it);

    while(it2 != s.end()){
        Sol = max(Sol, *it2 - *it);
        ++it2; ++it;
    }

    return Sol;
}

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