Submission #151832

#	Time	Username	Problem	Language	Result	Execution time	Memory
151832		SorahISA	Gap (APIO16_gap)	C++14	100 / 100	76 ms	3448 KiB

gap

#ifndef LOCAL
#include "gap.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL

long long t, n;
vector<long long> vcL;

void MinMax(long long a, long long b, long long &mn, long long &mx) {
	cout << "MinMax(" << a << ", " << b << "): ";
	bool MN = false, MX = false;
	for (int i = 0; i < n; ++i) {
		if (!MN and vcL[i] >= a and vcL[i] <= b) {
			mn = vcL[i];
			MN = true;
		}
		if (!MX and vcL[n - i - 1] <= b and vcL[n - i - 1] >= a) {
			mx = vcL[n - i - 1];
			MX = true;
		}
		if (MN and MX) {
			break;
		}
	}
	
	if (!MN or !MX) {
		mn = -1;
		mx = -1;
	}
	
	cout << "mn = " << mn << ", mx = " << mx << '\n';
	return;
}

#endif

const int maxn = 1E5 + 5;
vector<long long> num(maxn, -1);
long long mn, mx, cnt = 0;

long long findGap1(int N) {
	mn = -1;
	mx = (long long)1E18 + 2;
	
	for (int i = 0; i < (N+1)/2; ++i) {
		#ifdef LOCAL
		MinMax(mn + 1, mx - 1, mn, mx);
		#else
		MinMax(mn + 1, mx - 1, &mn, &mx);
		#endif
		
		num[i] = mn;
		num[N - i - 1] = mx;
		
		if (mn == -1 and mx == -1) assert(false);
		else if (mn == mx) break;
	}
	
	long long answer = 0;
	for (int i = 1; i < N; ++i) {
		answer = max(answer, num[i] - num[i - 1]);
	}
	
	return answer;
}

/*
void recur(long long lo, long long hi, long long &mn, long long &mx) {
	#ifdef LOCAL
	MinMax(lo, hi, mn, mx);
	#else
	MinMax(lo, hi, &mn, &mx);
	#endif
	
	if (mx == mn + 1) {
		num[cnt++] = mn;
		num[cnt++] = mx;
	}
	else if (mn != mx and mx != -1) {
		long long mi = (mn + mx) >> 1;
		long long tmpMN = mn, tmpMX = mx;
		recur(tmpMN, mi, mn, mx);
		recur(mi + 1, tmpMX, mn, mx);
	}
	else if (mn == mx and mx != -1) {
		num[cnt++] = mn;
	}
}
*/

long long findGap2(int N) {
	// recur(0, (long long)1E18, mn, mx);
	#ifdef LOCAL
	MinMax(0, (long long)1E18, mn, mx);
	#else
	MinMax(0, (long long)1E18, &mn, &mx);
	#endif
	
	long long LO = mn, HI = mx;
	num.assign(1, mn);
	
	long long block[N][2];
	block[0][1] = LO;
	for (int i = 1; i < N; ++i) {
		block[i][0] = block[i - 1][1] + 1;
		block[i][1] = block[i][0] + (HI - LO) / (N - 1) - ((HI - LO) % (N - 1) <= i);
		#ifdef LOCAL
		cout << block[i][0] << ' ' << block[i][1] << '\n';
		#endif
	}
	
	for (int i = 1; i < N; ++i) {
		#ifdef LOCAL
		MinMax(block[i][0], block[i][1], mn, mx);
		#else
		MinMax(block[i][0], block[i][1], &mn, &mx);
		#endif
		
		if (mn == mx and mn != -1) {
			num.push_back(mn);
		}
		else if (mn != mx) {
			num.push_back(mn);
			num.push_back(mx);
		}
	}
	
	num.push_back(HI);
	
	long long answer = 0;
	int sz = num.size();
	for (int i = 1; i < sz; ++i) {
		answer = max(answer, num[i] - num[i - 1]);
	}
	
	return answer;
}

long long findGap(int T, int N) {
	if (T == 1) return findGap1(N);
	else 	    return findGap2(N);
}

#ifdef LOCAL

int main() {
	long long ANSWER = 0;
	cin >> t >> n;
	
	vcL.assign(n, 0);
	for (int i = 0; i < n; ++i) {
		cin >> vcL[i];
		if (i) ANSWER = max(ANSWER, vcL[i] - vcL[i - 1]);
	}
	
	long long myAns = findGap(t, n);
	cout << "Your answer: " << myAns << '\n';
	cout << "Real answer: " << ANSWER << '\n';
	return 0;
}

#endif

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