Submission #315969

#	Time	Username	Problem	Language	Result	Execution time	Memory
315969		phathnv	Gap (APIO16_gap)	C++11	100 / 100	83 ms	3264 KiB

gap

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

typedef long long ll;

const ll INF = 1e18;

vector <ll> a;

ll findGap(int t, int n){
    if (t == 1){
        ll l = 0, r = INF;
        while (l <= r && n > 0){
            ll mn, mx;
            MinMax(l, r, &mn, &mx);
            if (mn == -1 && mx == -1)
                break;
            a.push_back(mn);
            n--;
            if (mx != mn){
                a.push_back(mx);
                n--;
            }
            l = mn + 1;
            r = mx - 1;
        }
        ll res = 0;
        sort(a.begin(), a.end());
        for(int i = 1; i < (int) a.size(); i++)
            res = max(res, a[i] - a[i - 1]);
        return res;
    } else {
        ll l, r, d, res;
        MinMax(0, INF, &l, &r);
        res = (r - l - n) / n;
        d = (r - l) / n;

        a.push_back(l);
        a.push_back(r);
        l++;
        r--;

        while (l <= r){
            ll mn, mx;
            MinMax(l, min(l + d, r), &mn, &mx);
            if (mn != -1 && mx != -1){
                a.push_back(mn);
                a.push_back(mx);
            }
            l += d + 1;
        }
        sort(a.begin(), a.end());
        for(int i = 1; i < (int) a.size(); i++)
            res = max(res, a[i] - a[i - 1]);
        return res;
    }
}

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