Submission #946437

#	Time	Username	Problem	Language	Result	Execution time	Memory
946437		n3rm1n	Gap (APIO16_gap)	C++17	30 / 100	31 ms	3460 KiB

gap

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

using namespace std;
const int MAXN = 2e5 + 10;
long long a[MAXN];
long long findGap(int T, int N)
{
	long long s = 0, t = (long long)(1e18);
	long long mn, mx;
	long long n = N;
	long long filled0 = 0, filled1 = n+1;

	while(filled0 + 1 <= filled1 - 1)
	{
	    ///cout << mn << " " << mx << endl;
	    MinMax(s, t, &mn, &mx);

	    if(mn == mx)
        {
            filled0 ++;
            a[filled0] = mn;
            n --;
            break;
        }
        filled0 ++;
        filled1 --;
        n-= 2;
        a[filled0] = mn;
        a[filled1] = mx;

        s = mn + 1;
        t = mx - 1;
	}
	long long ans = 0;
	//cout << "n is " << n << endl;
	//cout << a[1] << " ";
	for (int i = 2; i <= N; ++ i)
    {
        //cout << a[i] << " ";
        ans = max(ans, (long long) (a[i] - a[i-1]));
    }
    //cout << endl;
    //cout << ans << endl;
    return ans;
}

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