답안 #74596 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74596	2018-09-05T00:45:14 Z	tincamatei	Gap (APIO16_gap)	C++14	0 / 100	33 ms	3828 KB

#include <bits/stdc++.h>
 
#ifndef HOME
	#include "gap.h"
#else
 
long long findGap(int, int);
 
namespace grader {
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;
 
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;
}
 
void grader() {
	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, "Gap : %lld\n", findGap(subtask_num, N));
	fprintf(out, "Calls: %lld\n", call_count);
}
 
}
 
void MinMax(long long s, long long t, long long *mn, long long *mx) {
	grader::MinMax(s, t, mn, mx);
}
 
int main()
{
	grader::grader();
}
 
 
#endif
 
const int MAX_N = 100000;
const long long INF = 1000000000000000000;
 
long long v[MAX_N];
 
long long findGap(int T, int N) {
	int top = 0;
	long long mn, mx;
	MinMax(0, INF, &mn, &mx);
    long long expect = (mx - mn) / (N - 1);
    for(int i = 0; i < N - 1; ++i) {
	    MinMax(i * expect, i * expect - 1, &mn, &mx);
	    if(mn != -1)
	        v[top++] = mn;
	    if(mn != mx && mx != -1)
	        v[top++] = mx;
	}
	
	long long rez = 0LL;
	for(int i = 0; i < top - 1; ++i)
	    rez = std::max(rez, v[top + 1] - v[top]);
	return rez;
}

Subtask #1
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	376 KB	Execution failed because the return code was nonzero
2	Runtime error	2 ms	384 KB	Execution failed because the return code was nonzero
3	Runtime error	2 ms	596 KB	Execution failed because the return code was nonzero
4	Runtime error	2 ms	596 KB	Execution failed because the return code was nonzero
5	Runtime error	2 ms	596 KB	Execution failed because the return code was nonzero
6	Runtime error	2 ms	600 KB	Execution failed because the return code was nonzero
7	Runtime error	2 ms	620 KB	Execution failed because the return code was nonzero
8	Runtime error	2 ms	624 KB	Execution failed because the return code was nonzero
9	Runtime error	2 ms	628 KB	Execution failed because the return code was nonzero
10	Runtime error	2 ms	672 KB	Execution failed because the return code was nonzero
11	Runtime error	3 ms	676 KB	Execution failed because the return code was nonzero
12	Runtime error	3 ms	704 KB	Execution failed because the return code was nonzero
13	Runtime error	2 ms	732 KB	Execution failed because the return code was nonzero
14	Runtime error	3 ms	760 KB	Execution failed because the return code was nonzero
15	Runtime error	2 ms	788 KB	Execution failed because the return code was nonzero
16	Runtime error	9 ms	1444 KB	Execution failed because the return code was nonzero
17	Runtime error	9 ms	1912 KB	Execution failed because the return code was nonzero
18	Runtime error	9 ms	2372 KB	Execution failed because the return code was nonzero
19	Runtime error	9 ms	2836 KB	Execution failed because the return code was nonzero
20	Runtime error	6 ms	2916 KB	Execution failed because the return code was nonzero
21	Runtime error	32 ms	3712 KB	Execution failed because the return code was nonzero
22	Runtime error	30 ms	3728 KB	Execution failed because the return code was nonzero
23	Runtime error	32 ms	3728 KB	Execution failed because the return code was nonzero
24	Runtime error	32 ms	3728 KB	Execution failed because the return code was nonzero
25	Runtime error	22 ms	3728 KB	Execution failed because the return code was nonzero
26	Runtime error	30 ms	3728 KB	Execution failed because the return code was nonzero
27	Runtime error	31 ms	3728 KB	Execution failed because the return code was nonzero
28	Runtime error	32 ms	3732 KB	Execution failed because the return code was nonzero
29	Runtime error	30 ms	3732 KB	Execution failed because the return code was nonzero
30	Runtime error	19 ms	3732 KB	Execution failed because the return code was nonzero
31	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
32	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero

Subtask #2
0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
2	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
3	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
4	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
5	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
6	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
7	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
8	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
9	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
10	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
11	Runtime error	3 ms	3732 KB	Execution failed because the return code was nonzero
12	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
13	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
14	Runtime error	3 ms	3732 KB	Execution failed because the return code was nonzero
15	Runtime error	2 ms	3732 KB	Execution failed because the return code was nonzero
16	Runtime error	9 ms	3732 KB	Execution failed because the return code was nonzero
17	Runtime error	9 ms	3732 KB	Execution failed because the return code was nonzero
18	Runtime error	10 ms	3732 KB	Execution failed because the return code was nonzero
19	Runtime error	9 ms	3732 KB	Execution failed because the return code was nonzero
20	Runtime error	10 ms	3732 KB	Execution failed because the return code was nonzero
21	Runtime error	30 ms	3732 KB	Execution failed because the return code was nonzero
22	Runtime error	33 ms	3732 KB	Execution failed because the return code was nonzero
23	Runtime error	30 ms	3732 KB	Execution failed because the return code was nonzero
24	Runtime error	29 ms	3828 KB	Execution failed because the return code was nonzero
25	Runtime error	28 ms	3828 KB	Execution failed because the return code was nonzero
26	Runtime error	31 ms	3828 KB	Execution failed because the return code was nonzero
27	Runtime error	33 ms	3828 KB	Execution failed because the return code was nonzero
28	Runtime error	30 ms	3828 KB	Execution failed because the return code was nonzero
29	Runtime error	29 ms	3828 KB	Execution failed because the return code was nonzero
30	Runtime error	16 ms	3828 KB	Execution failed because the return code was nonzero
31	Runtime error	2 ms	3828 KB	Execution failed because the return code was nonzero
32	Runtime error	2 ms	3828 KB	Execution failed because the return code was nonzero

답안 #74596

Compilation message

Subtask #1 0 / 30.0

Subtask #2 0 / 70.0

Subtask #1
0 / 30.0

Subtask #2
0 / 70.0