Submission #170969

#	Time	Username	Problem	Language	Result	Execution time	Memory
170969		osaaateiasavtnl	Gap (APIO16_gap)	C++17	100 / 100	73 ms	2680 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7;
const int T = 1000 * 1000 * 1000;
const int INF = T * T;
int al[N], ar[N];
long long findGap(signed group, signed n)
{
    if (group == 2) {
        int l, r;
        MinMax(0, INF, &l, &r);

        if (n == 2)
            return r - l;

        int len = r - l + 1;
        int k = len % (n - 1);
        int t = len / (n - 1) + 1;
        
        int ptr = l;
        for (int i = 0; i < k; ++i) {
            MinMax(ptr, ptr + t - 1, &al[i], &ar[i]);
            ptr += t;
        }   
        --t;
        for (int i = k; i < n - 1; ++i) {
            MinMax(ptr, ptr + t - 1, &al[i], &ar[i]);
            ptr += t;
        }   

        int ans = 0;
        r = -1;
        for (int i = 0; i < n - 1; ++i) {
            if (al[i] == -1)
                continue;
            if (r != -1) 
                ans = max(ans, al[i] - r);
            r = ar[i];
        }   
        return ans;
    }
    else {
        int l = -1, r = INF + 1;
        int ans = 0;
        for (int i = 0; i < (n + 1) / 2; ++i) {
            int nl, nr;
            MinMax(l + 1, r - 1, &nl, &nr);
            if (nl == -1) {
                break;
            }
            else {
                if (l != -1)
                    ans = max(ans, nl - l);
                if (r != INF + 1)
                    ans = max(ans, r - nr);
                l = nl;
                r = nr;
            }   
        }   
        ans = max(ans, r - l);
        return ans;
    }
}

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