Submission #151765

#	Time	Username	Problem	Language	Result	Execution time	Memory
151765		SorahISA	Gap (APIO16_gap)	C++14	0 / 100	52 ms	3964 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) {
			mn = vcL[i];
			MN = true;
		}
		if (!MX and vcL[n - i - 1] <= b) {
			mx = vcL[n - i - 1];
			MX = true;
		}
		if (MN and MX) {
			break;
		}
	}
	
	cout << "mn = " << mn << ", mx = " << mx << '\n';
	return;
}

#endif

long long findGap1(int N)
{
	vector<long long> num(N, -1);
	long long 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;
}

long long findGap2(int N)
{
	vector<long long> num(N, -1);
	long long mn = -1, mx = (long long)1E18 + 2;
	for (int i = 0; i < 40000; ++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 < 40000; ++i) {
		answer = max(answer, num[i] - num[i - 1]);
	}
	for (int i = N-39999; i < N; ++i) {
		answer = max(answer, num[i] - num[i - 1]);
	}
	
	return answer;
}

long long findGap(int T, int N) {
	if (N <= 80000) 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: 0 / 30
• Subtask 2: 0 / 70