Submission #41261

#	Time	Username	Problem	Language	Result	Execution time	Memory
41261		Just_Solve_The_Problem	Gap (APIO16_gap)	C++11	100 / 100	74 ms	2252 KiB

gap

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

#define ll long long
#define ok puts("ok");

const int inf = (int)1e9 + 7;

using namespace std;

ll solve1(int n) {
	long long left;
	long long right;
	left = 0;
	right = 1e18;
	long long mn = 0, mx = 1e18;        
	long long vec[n];
	int cnt = 0;
	int cn = n - 1;
	while (cnt <= cn) {
		MinMax(left, right, &mn, &mx);
		vec[cnt++] = mn; 
		if (mn != mx)
			vec[cn--] = mx;
		left = mn + 1;
		right = mx - 1;	
	}                  
	long long ans = 0;
	for (int i = 1; i < n; i++) {         
		if (vec[i] - vec[i - 1] > ans) {
			ans = vec[i] - vec[i - 1];
		}
	}
	return ans;
}

ll findGap(int t, int n) {
	if (t == 1) {
		return solve1(n);
	}
	ll l, r;
	MinMax(0, 1e18, &l, &r);
	if (n == 2) {
		return r - l;
	} else if (r - l + 1 == n) {
		return 1;
	}
	if(r - l + 1 == n + 1) {
		return 2;
	}
	ll dif = (r - l + 1) / (n + 1);
	ll x = (r - l + 1) % (n + 1);
	if (x) dif++;
	else x = inf;
	ll start = l;
	ll fin = start + dif - 1;
	ll fre = 0;
	ll mx = 0; 
	ll ans = 0;
	ll blockes = 0;
	ll l1, r1;
	while (1) {
		blockes++;
		if (blockes == 1) {        
			if (dif == 1) {
				l1 = r1 = l;
			} else {
				MinMax(start + 1, fin, &l1, &r1);
				l1 = l;
				if (r1 == -1) r1 = l;
			}
		} else if (blockes == n + 1) {						
			if (dif == 1) {
				
				l1 = r1 = r;
			} else {
				MinMax(start, fin - 1, &l1, &r1);
				r1 = r;
				if (l1 == -1) l1 = r;
			}
		} else {
			MinMax(start, fin, &l1, &r1);
		}

		x--;
		// printf("#blocks %lld\n", blockes);
		// cout << blockes << ' ' << dif << endl;
		// cout << start << ' ' << fin << endl;
		// cout << l1 << ' ' << r1 << endl;
		if (l1 == -1) {
			fre += dif;
		} else {
			if (fre != 0) {
				ans = max(ans, fre + mx + (l1 - start + 1));
			}
			fre = 0;             
			mx = fin - r1;
		}
		if (fin == r) break;
		if (x <= 0) {
			dif--;
			x = inf;
		}      
		start = fin + 1;
		fin = min(start + dif - 1, r);
	}
	return ans;
}

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