Submission #712716

#	Time	Username	Problem	Language	Result	Execution time	Memory
712716		hoainiem	Gap (APIO16_gap)	C++14	89.04 / 100	53 ms	1884 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define nmax 100008
const long long inf = 1e18;
using namespace std;
long long ans = -1, a[nmax];
long long findGap(int T, int n)
{
    if (T == 1){
        a[0] = -1;
        a[n + 1] = inf;
        a[n + 1] += 8;
        for (int i = 1, j = n; i <= j; i++, j--){
            if (i < j)
                MinMax(a[i - 1] + 1, a[j + 1] - 1, &a[i], &a[j]);
            else
                MinMax(a[i - 1] + 1, a[j + 1] - 1, &a[i], &a[n + 2]);
        }

        for (int i = 1; i < n; i++)
            ans = max(ans, a[i + 1] - a[i]);
    }
    else{
        long long u, v, blk, x, y, pre;
        MinMax(0, inf + 8, &u, &v);
        blk = (v - u) / (n - 1);
        pre = u;
        if (n == 2)
            return v - u;
        for (long long l = u + 1, r = u + 1 + blk; l < v; l += blk, r += blk){
            if (r >= v)
                r = v;
            if (l >= r)
                break;
            MinMax(l, r - 1, &x, &y);
            if (x == -1 && y == -1)
                continue;
            ans = max(ans, x - pre);
            pre = y;
        }
        ans = max(ans, v - pre);
    }
	return ans;
}

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