답안 #101884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101884 2019-03-20T17:40:34 Z KCSC Gap (APIO16_gap) C++14
100 / 100
73 ms 3064 KB
#ifndef HOME
	#include "gap.h"
#endif

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

#ifdef HOME
const int DIM = 100005;

long long arr[DIM]; int N;

void MinMax(long long a, long long b, long long *mn, long long *mx) {
	mn = 1LL << 60, mx = -1LL << 60;
	for (int i = 1; i <= N; ++i) {
		if (arr[i] >= a and arr[i] <= b) {
			mn = min(mn, arr[i]); mx = max(mx, arr[i]); } } 
	if (mn > mx) {
		mn = mx = -1; } }
#endif

long long findGap(int t, int n) {
	long long mn, mx, ans = 0;
	MinMax(0, 1LL << 60, &mn, &mx);
	if (t == 1) {
		for (int i = 1; i < (n + 1) / 2; ++i) {
			long long mn2, mx2;
			MinMax(mn + 1, mx - 1, &mn2, &mx2);
			ans = max(ans, mn2 - mn); ans = max(ans, mx - mx2);
			mn = mn2; mx = mx2; }
		ans = max(ans, mx - mn); }
	else {
		long long sz = (mx - mn + n - 1) / n, ls = mn;
		for (long long st = mn + 1, en = mn + sz, i = 1; i <= n; st += sz, en += sz, ++i) {
			if (en > mx - 1) { en = mx - 1; }
			if (st > en) { break; }
			long long mn2, mx2;
			MinMax(st, en, &mn2, &mx2);
			if (mn2 != -1) {
				ans = max(ans, mn2 - ls); ls = mx2; } }
		ans = max(ans, mx - ls); }
	return ans; }

#ifdef HOME
int main(void) {
	freopen("gap.in", "r", stdin);
	freopen("gap.out", "w", stdout);
	int n; cin >> n; N = n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i]; }
	sort(arr + 1, arr + n + 1);
	cout << findGap(1, n) << " " << findGap(2, n) << endl;
	return 0; }
#endif
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 14 ms 896 KB Output is correct
17 Correct 14 ms 988 KB Output is correct
18 Correct 15 ms 1024 KB Output is correct
19 Correct 14 ms 1024 KB Output is correct
20 Correct 11 ms 640 KB Output is correct
21 Correct 50 ms 2940 KB Output is correct
22 Correct 51 ms 2936 KB Output is correct
23 Correct 49 ms 2948 KB Output is correct
24 Correct 48 ms 3036 KB Output is correct
25 Correct 41 ms 2304 KB Output is correct
26 Correct 49 ms 2944 KB Output is correct
27 Correct 51 ms 2948 KB Output is correct
28 Correct 53 ms 2944 KB Output is correct
29 Correct 55 ms 2960 KB Output is correct
30 Correct 35 ms 1792 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 19 ms 1024 KB Output is correct
17 Correct 19 ms 1024 KB Output is correct
18 Correct 20 ms 1024 KB Output is correct
19 Correct 21 ms 892 KB Output is correct
20 Correct 11 ms 640 KB Output is correct
21 Correct 69 ms 2936 KB Output is correct
22 Correct 69 ms 2936 KB Output is correct
23 Correct 73 ms 2984 KB Output is correct
24 Correct 72 ms 2940 KB Output is correct
25 Correct 64 ms 2304 KB Output is correct
26 Correct 72 ms 2936 KB Output is correct
27 Correct 72 ms 2936 KB Output is correct
28 Correct 71 ms 3064 KB Output is correct
29 Correct 69 ms 2936 KB Output is correct
30 Correct 43 ms 1784 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct