Submission #1147799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147799		njoop	Gap (APIO16_gap)	C++17	30 / 100	2097 ms	2240 KiB

gap

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

long long mx, mn, l, r;
vector<long long> arr;

long long findAns() {
    long long ans = 0;
    sort(arr.begin(), arr.end());
    for(int i=0; i<arr.size()-1; i++) {
        ans = max(ans, arr[i+1]-arr[i]);
    }
    return ans;
}

long long findGap(int T, int N) {
    l=0; r=1e18;
    if(T == 1) {
        for(int i=1; i<=N/2; i++) {
            MinMax(l, r, &mn, &mx);
            if(mn == -1 || mx == -1) {
                break;
            }
            arr.push_back(mn);
            arr.push_back(mx);
            l = mn+1;
            r = mx-1;
        }
        if(N%2 == 1) {
            MinMax(l, r, &mn, &mx);
            arr.push_back(mn);
        }
        return findAns();
    }
    MinMax(l, r, &mn, &mx);
    l = mn;
    r = mx;
    arr.push_back(mn);
    arr.push_back(mx);
    long long in = (r-l)/(N-1) + (r-l)%(N-1);
    for(int j=l+1; j<r; j+=in+1) {
        if(arr.size() > 10000) {
            return 0;
        }
        MinMax(j, j+in, &mn, &mx);
        if(mn != -1 && mx != -1) {
            arr.push_back(mn);
            arr.push_back(mx);
        }
    }
    return findAns();
}

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