Submission #712712

#	Time	Username	Problem	Language	Result	Execution time	Memory
712712		hoainiem	Gap (APIO16_gap)	C++14	30 / 100	63 ms	1864 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;
        for (long long l = u, r = u + blk; l < v; l += blk, r += blk){
            if (r >= v)
                r = v - 1;
            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: 0 / 70