Submission #1176032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176032		n3rm1n	Gap (APIO16_gap)	C++17	0 / 100	143 ms	2240 KiB

gap

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

pair < long long, long long > ask(long long l, long long r)
{
    long long mn, mx;
    MinMax(l, r, &mn, &mx);
    return make_pair(mn, mx);
}
long long findGap(int T, int N)
{

    pair < long long, long long > initial = ask(1LL * 0, 1LL * 1e18);
    long long l = initial.first, r = initial.second;
   /// cout << l << " " << r << endl;
    long long sz = N, len, range;
    vector < long long > g;
    g.push_back(l);
    while(l < r)
    {
        len = r - l + 1;
        if(sz == 1)range = len;
        else range = max(1LL * 1, (len - sz) / (sz-1));
        pair < long long , long long > values = ask(l + 1, min(r, l + range));
        if(values.first == -1)l = min(l + range, r);
        else
        {
            sz --;
            g.push_back(values.second);
            ///cout << "NOTICED "  << values.second << endl;
            l = values.second;
        }
    }
    ///cout << "finished " << endl;
    g.push_back(r);
    long long maxspace = 0;
    for (int i = 0; i < g.size()-1; ++ i)
    {
        long long space = g[i+1] - g[i];
        ///cout << space << " " << g[i] << " and " << g[i+1] << endl;
        maxspace = max(maxspace, space);
    }
    return maxspace;
}

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