답안 #110696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110696	2019-05-12T06:10:26 Z	baneling100	Gap (APIO16_gap)	C++17	100 / 100	89 ms	2044 KB

gap

#include "gap.h"
#include <algorithm>
#define MAX_N 100000
#define MAX_A 1000000000000000000

long long A[MAX_N];

long long findGap(int T, int N) {
    
    long long min, max, ans = 0;
    
    if (T == 1) { // subtask 1
        int t = (N + 1) / 2, low = 0, high = N;
        min = -1, max = MAX_A + 1;
        
        for(int i = 0; i < t; i++) {
            MinMax(min + 1, max - 1, &min, &max);        
            A[low++] = min;
            A[--high] = max;
        }
        
        for(int i = 1; i < N; i++)
            if(ans < A[i] - A[i - 1])
                ans = A[i] - A[i - 1];
    }
    else { // subtask 2
        MinMax(0, MAX_A, &min, &max);
        long long gap = (max - min) / N, x, y, start = min + 1, end;
        int M = 0;
        A[M++] = min;
        while(start < max) {
            x = y = -1;
            end = std::min(start + gap, max - 1);
            MinMax(start, end, &x, &y);
            if(x != -1) {
                A[M++] = x;
                if(x < y) A[M++] = y;
            }
            start = end + 1;
        }
        A[M++] = max;
        for(int i = 1; i < M; i++)
            if(ans < A[i] - A[i - 1])
                ans = A[i] - A[i - 1];
    }
    
	return ans;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	256 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	256 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	3 ms	384 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	2 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	16 ms	768 KB	Output is correct
17	Correct	17 ms	768 KB	Output is correct
18	Correct	13 ms	640 KB	Output is correct
19	Correct	14 ms	640 KB	Output is correct
20	Correct	10 ms	640 KB	Output is correct
21	Correct	52 ms	1912 KB	Output is correct
22	Correct	54 ms	1852 KB	Output is correct
23	Correct	51 ms	1920 KB	Output is correct
24	Correct	50 ms	1912 KB	Output is correct
25	Correct	41 ms	1912 KB	Output is correct
26	Correct	67 ms	1884 KB	Output is correct
27	Correct	59 ms	2040 KB	Output is correct
28	Correct	51 ms	1860 KB	Output is correct
29	Correct	49 ms	2044 KB	Output is correct
30	Correct	41 ms	1920 KB	Output is correct
31	Correct	3 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	256 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	256 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	2 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	640 KB	Output is correct
17	Correct	18 ms	640 KB	Output is correct
18	Correct	19 ms	728 KB	Output is correct
19	Correct	16 ms	768 KB	Output is correct
20	Correct	9 ms	512 KB	Output is correct
21	Correct	61 ms	1784 KB	Output is correct
22	Correct	61 ms	1784 KB	Output is correct
23	Correct	69 ms	1840 KB	Output is correct
24	Correct	61 ms	1784 KB	Output is correct
25	Correct	89 ms	1912 KB	Output is correct
26	Correct	68 ms	1884 KB	Output is correct
27	Correct	62 ms	1812 KB	Output is correct
28	Correct	70 ms	1784 KB	Output is correct
29	Correct	73 ms	1876 KB	Output is correct
30	Correct	32 ms	1272 KB	Output is correct
31	Correct	2 ms	256 KB	Output is correct
32	Correct	2 ms	256 KB	Output is correct