Submission #41256

#	Time	Username	Problem	Language	Result	Execution time	Memory
41256		Just_Solve_The_Problem	Gap (APIO16_gap)	C++11	0 / 100	92 ms	2248 KiB

gap

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

// #include "grader.cpp"

#define ll long long

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 (mn < mx) {
		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;
	l++; r--;
	ll start = l;
	ll fin = start + dif - 1;
	ll fre = 0;
	ll mx = 0; 
	ll ans = 0;
	while (1) {
		ll l1, r1;
		MinMax(start, fin, &l1, &r1);
		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;      
		start = fin + 1;
		fin = min(start + dif - 1, r);
	}
	return ans;
}

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