Submission #1176052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176052		n3rm1n	Gap (APIO16_gap)	C++17	70 / 100	43 ms	2320 KiB

gap

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

pair < long long, long long > ask(long long l, long long r)
{
    if(l > r)return make_pair(-1, -1);
    long long mn, mx;
    MinMax(l, r, &mn, &mx);
    return make_pair(mn, mx);
}
long long findGap(int T, int N)
{
    if(T == 1)
    {
        long long l = 0, r = 1LL * 1e18;
        vector < long long > g;
        while(l != r)
        {
            pair < long long, long long> curr = ask(l + 1, r - 1);
            if(curr.first == -1)break;
            l = curr.first;
            r = curr.second;
            g.push_back(l);
            g.push_back(r);
        }
        sort(g.begin(), g.end());
        long long maxspace = 0;
        for (int i = 0; i < g.size()-1; ++ i)
        {
            long long space = g[i+1] - g[i];
            maxspace = max(maxspace, space);
        }
        return maxspace;
    }
    pair < long long, long long > initial = ask(1LL * 0, 1LL * 1e18);
    long long l = initial.first, r = initial.second;
    long long sz = N, len;
    vector < long long > g;
    g.push_back(l);
    len = r - l + 1;
    long long ans = 0;
    long long range = max(1LL * 1, (len) / (sz) + 1);

    long long last = l;
    while(l < r)
    {
        pair < long long , long long > values = ask(l + 1,  l + 1 + range);
        if(values.first != -1)
        {

            sz --;
            ans = max(ans, values.first - last);
            last = values.second;
        }
        l = l + 1 + range;
    }
    long long maxspace = 0;
    return ans;
}

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