Submission #105977

#	Time	Username	Problem	Language	Result	Execution time	Memory
105977		Hideo	Gap (APIO16_gap)	C++14	100 / 100	88 ms	2812 KiB

gap

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "gap.h"

using namespace std;

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pl pair < ll, ll >
#define pii pair < int, pl >
#define vii vector < pl >

const int MAXN = 1e5 + 7;
const ll INF = 1e18;

ll mn, mx, l, ans;
ll s, f, sz, r;

pl a[MAXN];

long long findGap(int T, int N){
	if (T == 1){
        l = 1, r = N, f = INF;
        while (r >= l){
            MinMax(s, f, &mn, &mx);
            f = mx - 1;
            s = mn + 1;
            a[l].fr = mn; a[r].fr = mx;
            l++; r--;
        }
        for (int i = 2; i <= N; i++)
            ans = max(ans, a[i].fr - a[i - 1].fr);
	}
	else {
        MinMax(0, INF, &s, &f);
        sz = (f - s - 1) / (N - 1);
        r = (f - s - 1) % (N - 1);
        a[1] = {s, s};
        a[N + 1] = {f, f};
        l = s + 1;
        for (int i = 2; i <= N; i++){
            if (r){
                r--;
                MinMax(l, l + sz, &mn, &mx);
                if (mn != -1)
                    a[i] = {mn, mx};
                else
                    a[i] = a[i - 1];
                l = l + sz + 1;
            }
            else {
                MinMax(l, l + sz - 1, &mn, &mx);
                if (mn != -1)
                    a[i] = {mn, mx};
                else
                    a[i] = a[i - 1];
                l = l + sz;
            }
            ans = max(ans, a[i].fr - a[i - 1].sc);
        }
        ans = max(ans, a[N + 1].fr - a[N].sc);

	}
	return ans;
}

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