답안 #966470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
966470 2024-04-20T00:55:26 Z PenguinsAreCute Gap (APIO16_gap) C++17
30 / 100
2000 ms 3108 KB
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
/*
static void my_assert(int k){ if (!k) exit(1); }

static int subtask_num, N;
static long long A[100001];
static long long call_count;

long long findGap(int, int);

void MinMax(long long s, long long t, long long *mn, long long *mx)
{
	int lo = 1, hi = N, left = N+1, right = 0;
	my_assert(s <= t && mn != NULL && mx != NULL);
	while (lo <= hi){
		int mid = (lo+hi)>>1;
		if (A[mid] >= s) hi = mid - 1, left = mid;
		else lo = mid + 1;
	}
	lo = 1, hi = N;
	while (lo <= hi){
		int mid = (lo+hi)>>1;
		if (A[mid] <= t) lo = mid + 1, right = mid;
		else hi = mid - 1;
	}
	if (left > right) *mn = *mx = -1;
	else{
		*mn = A[left];
		*mx = A[right];
	}
	if (subtask_num == 1) call_count++;
	else if (subtask_num == 2) call_count += right-left+2;
}
*/
ll findGap(int T, int N) {
    if(T==1) {
        ll mn, mx, ans = 0;
        MinMax(0,1e18,&mn,&mx);
        //if(N==2) {return mx-mn;}
        for(int i=0;i<(N-1)/2;i++) {
            ll nMn, nMx;
            MinMax(mn+1,mx-1,&nMn,&nMx);
            ans=max({ans,nMn-mn,mx-nMx});
            mn=nMn;
            mx=nMx;
        }
        ans=max(ans,mx-mn);
        return ans;
    } else {
        ll mn, mx, cur = -1;
        MinMax(0,1e18,&mn,&mx);
        ll b = (mx - mn + (N-2)) / (N-1);
        ll ans = b;
        for(int i=mn;i<mx;i+=b) {
            ll nMn, nMx;
            MinMax(i,i+b-1,&nMn,&nMx);
            if(cur!=-1 && nMn!=-1) ans=max(ans,nMn-cur);
            if(nMx != -1) cur = nMx;
        }
        ans = max(ans, mx - cur);
        return ans;
    }
}
/*
int main()
{
	FILE *in = stdin, *out = stdout;
	my_assert(2 == fscanf(in, "%d%d", &subtask_num, &N));
	my_assert(1 <= subtask_num && subtask_num <= 2);
	my_assert(2 <= N && N <= 100000);
	for (int i=1;i<=N;i++) my_assert(1 == fscanf(in, "%lld", A+i));
	for (int i=1;i<N;i++) my_assert(A[i] < A[i+1]);
	fprintf(out, "%lld\n", findGap(subtask_num, N));
	fprintf(out, "%lld\n", call_count);
}
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 2 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 7 ms 2580 KB Output is correct
17 Correct 8 ms 2580 KB Output is correct
18 Correct 9 ms 2584 KB Output is correct
19 Correct 8 ms 2680 KB Output is correct
20 Correct 7 ms 2572 KB Output is correct
21 Correct 29 ms 2852 KB Output is correct
22 Correct 30 ms 2848 KB Output is correct
23 Correct 31 ms 2856 KB Output is correct
24 Correct 30 ms 2868 KB Output is correct
25 Correct 27 ms 2852 KB Output is correct
26 Correct 29 ms 3108 KB Output is correct
27 Correct 30 ms 3024 KB Output is correct
28 Correct 29 ms 2856 KB Output is correct
29 Correct 29 ms 2856 KB Output is correct
30 Correct 25 ms 2860 KB Output is correct
31 Correct 1 ms 2392 KB Output is correct
32 Correct 1 ms 2392 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3028 ms 2392 KB Time limit exceeded
2 Execution timed out 3048 ms 2392 KB Time limit exceeded
3 Execution timed out 3019 ms 2392 KB Time limit exceeded
4 Execution timed out 3051 ms 2392 KB Time limit exceeded
5 Correct 0 ms 2392 KB Output is correct
6 Execution timed out 3049 ms 2392 KB Time limit exceeded
7 Execution timed out 3054 ms 2392 KB Time limit exceeded
8 Execution timed out 3049 ms 2392 KB Time limit exceeded
9 Execution timed out 3098 ms 2392 KB Time limit exceeded
10 Correct 0 ms 2392 KB Output is correct
11 Execution timed out 3075 ms 2392 KB Time limit exceeded
12 Execution timed out 3036 ms 2392 KB Time limit exceeded
13 Execution timed out 3068 ms 2392 KB Time limit exceeded
14 Execution timed out 3031 ms 2392 KB Time limit exceeded
15 Execution timed out 3031 ms 2392 KB Time limit exceeded
16 Execution timed out 3058 ms 2584 KB Time limit exceeded
17 Execution timed out 3041 ms 2584 KB Time limit exceeded
18 Execution timed out 3056 ms 2584 KB Time limit exceeded
19 Execution timed out 3056 ms 2588 KB Time limit exceeded
20 Correct 6 ms 2572 KB Output is correct
21 Execution timed out 3040 ms 2852 KB Time limit exceeded
22 Execution timed out 3060 ms 2852 KB Time limit exceeded
23 Execution timed out 3040 ms 2864 KB Time limit exceeded
24 Execution timed out 3014 ms 3100 KB Time limit exceeded
25 Execution timed out 3059 ms 2848 KB Time limit exceeded
26 Execution timed out 3062 ms 2860 KB Time limit exceeded
27 Execution timed out 3010 ms 2856 KB Time limit exceeded
28 Execution timed out 3012 ms 2856 KB Time limit exceeded
29 Execution timed out 3027 ms 2860 KB Time limit exceeded
30 Correct 23 ms 2852 KB Output is correct
31 Execution timed out 3061 ms 2392 KB Time limit exceeded
32 Execution timed out 3019 ms 2392 KB Time limit exceeded