Submission #609672

#	Time	Username	Problem	Language	Result	Execution time	Memory
609672		AugustinasJucas	Gap (APIO16_gap)	C++14	8.56 / 100	159 ms	6980 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

int n;
set<long long> setas;
long long rnd(long long L, long long R) {
    long long sk = rand() % 1000000007ll;
    sk = sk * (rand() % 1000000007ll);

    return L + sk % (R - L + 1);
}
void calc(long long L, long long R) {
    if(L > R) return ;
    long long mn, mx;
    MinMax(L, R, &mn, &mx);
    if(mn == -1) return ;

    long long mid = rnd(L, R);
    long long MX = mx;
    long long sk = -1;
    MinMax(mid, R, &mn, &mx);
    if(mn == -1) {
        sk = MX;
        calc(L, MX-1);
    }else {
        sk = mn;
        calc(L, sk-1);
        calc(mid+1, mx-1);
        setas.insert(mx);
    }
    setas.insert(sk);



}

long long findGap(int T, int N) {
    srand(time(0));
    n = N;
    long long L = 0, R = 1e18;
    calc(L, R);
    vector<long long> mas;
    for(auto x : setas) mas.push_back(x);

    long long ans = 0;
    for(int i = 0; i < n-1; i++) {
        ans = max(ans, mas[i+1] - mas[i]);
    }
    return ans;
}

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