답안 #94063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94063	2019-01-15T15:14:42 Z	Kastanda	Gap (APIO16_gap)	C++11	100 / 100	67 ms	4584 KB

gap

#include<bits/stdc++.h>
#include "gap.h"
#define pb push_back
using namespace std;
typedef long long ll;
long long findGap(int T, int N)
{
    if (T == 1)
    {
        int l = 1, r = N;
        ll le = 0, ri = 1e18;
        ll Mn, Mx;
        vector < ll > A(N + 1);
        while (l <= r)
        {
            MinMax(le, ri, &Mn, &Mx);
            A[l ++] = Mn; A[r --] = Mx;
            le = Mn + 1; ri = Mx - 1;
        }
        Mx = 0;
        for (int i = 1; i < N; i++)
            Mx = max(Mx, A[i + 1] - A[i]);
        return Mx;
    }
    ll Mn, Mx;
    ll le = 0, ri = 1e18;
    MinMax(le, ri, &Mn, &Mx);
    if (Mx - Mn <= N - 1)
        return 1LL;
    ll len = (Mx - Mn - 1) / (N - 1);
    ll cnt = (Mx - Mn - 1) % (N - 1);
 
    le = Mn + 1;
    ll last = Mx;
    vector < ll > A = {Mn};
    for (int i = 1; i <= N - 1; i++)
    {
        ri = le + len - 1;
        if (i <= cnt)
            ri ++;
        MinMax(le, ri, &Mn, &Mx);
        le = ri + 1;
        if (Mn == -1)
            continue;
        A.pb(Mn);
        A.pb(Mx);
    }
    A.pb(last); Mx = 0;
    for (int i = 1; i < (int)A.size(); i += 2)
        Mx = max(Mx, A[i] - A[i - 1]);
    return Mx;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	14 ms	1144 KB	Output is correct
17	Correct	13 ms	1148 KB	Output is correct
18	Correct	14 ms	1144 KB	Output is correct
19	Correct	13 ms	1276 KB	Output is correct
20	Correct	10 ms	888 KB	Output is correct
21	Correct	49 ms	3704 KB	Output is correct
22	Correct	48 ms	3832 KB	Output is correct
23	Correct	48 ms	3832 KB	Output is correct
24	Correct	49 ms	3960 KB	Output is correct
25	Correct	41 ms	3192 KB	Output is correct
26	Correct	49 ms	3704 KB	Output is correct
27	Correct	48 ms	3832 KB	Output is correct
28	Correct	48 ms	3704 KB	Output is correct
29	Correct	48 ms	3704 KB	Output is correct
30	Correct	36 ms	2552 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	420 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	3 ms	504 KB	Output is correct
16	Correct	17 ms	1400 KB	Output is correct
17	Correct	17 ms	1400 KB	Output is correct
18	Correct	17 ms	1400 KB	Output is correct
19	Correct	18 ms	1400 KB	Output is correct
20	Correct	8 ms	760 KB	Output is correct
21	Correct	65 ms	4180 KB	Output is correct
22	Correct	65 ms	4208 KB	Output is correct
23	Correct	66 ms	4076 KB	Output is correct
24	Correct	64 ms	4080 KB	Output is correct
25	Correct	64 ms	4584 KB	Output is correct
26	Correct	66 ms	4080 KB	Output is correct
27	Correct	65 ms	4080 KB	Output is correct
28	Correct	66 ms	4332 KB	Output is correct
29	Correct	67 ms	4080 KB	Output is correct
30	Correct	34 ms	2168 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	376 KB	Output is correct