답안 #84387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84387	2018-11-14T21:30:01 Z	Alexa2001	Gap (APIO16_gap)	C++17	100 / 100	102 ms	3564 KB

gap

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll lim = 1e18;

long long findGap(int T, int N)
{
    ll *A, *B;
    ll ans = 0;
    A = new ll(); B = new ll();

    if(T == 1)
    {
        ll x = 0, y = lim;
        int i;
        for(i=0; i<(N+1)/2; ++i)
        {
            MinMax(x, y, A, B);
            if(i)
            {
                ans = max(ans, *A - x + 1);
                ans = max(ans, y - *B + 1);
            }
            x = *A + 1;
            y = *B - 1;
        }
        if(N%2==0) ans = max(ans, y-x+2);
        return ans;
    }

    MinMax(0, lim, A, B);
    ll X, Y;
    X = *A, Y = *B;

    ll i, S = (Y-X) / (N-1) + 1;
    vector<ll> endpoints;

    for(i = 0; i <= Y-X; i += S)
    {
        MinMax(X+i, X + min(i+S-1, Y-X), A, B);
        if(*A == -1) continue;
        endpoints.push_back(*A);
        endpoints.push_back(*B);
    }
    endpoints.push_back(Y);

    int j;
    for(j=0; j<endpoints.size()-1; ++j)
        ans = max(ans, endpoints[j+1] - endpoints[j]);
    return ans;
}

Compilation message

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0; j<endpoints.size()-1; ++j)
              ~^~~~~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	372 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	2 ms	592 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	2 ms	600 KB	Output is correct
7	Correct	2 ms	600 KB	Output is correct
8	Correct	2 ms	600 KB	Output is correct
9	Correct	2 ms	684 KB	Output is correct
10	Correct	2 ms	684 KB	Output is correct
11	Correct	3 ms	684 KB	Output is correct
12	Correct	3 ms	684 KB	Output is correct
13	Correct	2 ms	684 KB	Output is correct
14	Correct	3 ms	684 KB	Output is correct
15	Correct	3 ms	684 KB	Output is correct
16	Correct	14 ms	760 KB	Output is correct
17	Correct	14 ms	760 KB	Output is correct
18	Correct	14 ms	888 KB	Output is correct
19	Correct	14 ms	904 KB	Output is correct
20	Correct	12 ms	904 KB	Output is correct
21	Correct	53 ms	1400 KB	Output is correct
22	Correct	54 ms	1420 KB	Output is correct
23	Correct	54 ms	1420 KB	Output is correct
24	Correct	58 ms	1420 KB	Output is correct
25	Correct	46 ms	1528 KB	Output is correct
26	Correct	56 ms	1528 KB	Output is correct
27	Correct	54 ms	1528 KB	Output is correct
28	Correct	54 ms	1528 KB	Output is correct
29	Correct	53 ms	1528 KB	Output is correct
30	Correct	39 ms	1528 KB	Output is correct
31	Correct	2 ms	1528 KB	Output is correct
32	Correct	2 ms	1528 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1528 KB	Output is correct
2	Correct	2 ms	1528 KB	Output is correct
3	Correct	2 ms	1528 KB	Output is correct
4	Correct	2 ms	1528 KB	Output is correct
5	Correct	2 ms	1528 KB	Output is correct
6	Correct	2 ms	1528 KB	Output is correct
7	Correct	2 ms	1528 KB	Output is correct
8	Correct	2 ms	1528 KB	Output is correct
9	Correct	2 ms	1528 KB	Output is correct
10	Correct	2 ms	1528 KB	Output is correct
11	Correct	4 ms	1528 KB	Output is correct
12	Correct	3 ms	1528 KB	Output is correct
13	Correct	3 ms	1528 KB	Output is correct
14	Correct	3 ms	1528 KB	Output is correct
15	Correct	3 ms	1528 KB	Output is correct
16	Correct	19 ms	1528 KB	Output is correct
17	Correct	19 ms	1528 KB	Output is correct
18	Correct	20 ms	1528 KB	Output is correct
19	Correct	20 ms	1528 KB	Output is correct
20	Correct	10 ms	1528 KB	Output is correct
21	Correct	102 ms	2548 KB	Output is correct
22	Correct	75 ms	2660 KB	Output is correct
23	Correct	75 ms	2660 KB	Output is correct
24	Correct	74 ms	2660 KB	Output is correct
25	Correct	70 ms	3564 KB	Output is correct
26	Correct	80 ms	3564 KB	Output is correct
27	Correct	81 ms	3564 KB	Output is correct
28	Correct	75 ms	3564 KB	Output is correct
29	Correct	78 ms	3564 KB	Output is correct
30	Correct	39 ms	3564 KB	Output is correct
31	Correct	2 ms	3564 KB	Output is correct
32	Correct	2 ms	3564 KB	Output is correct