답안 #78113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78113	2018-10-02T12:53:17 Z	aquablitz11	Gap (APIO16_gap)	C++14	100 / 100	84 ms	39848 KB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;

using ll = long long;
const int N = 1e5+10;
ll A[N];

long long findGap(int t, int n)
{
    if (t == 1) {
        ll mn = 0, mx = 1e18;
        for (int i = 1; i <= (n+1)/2; ++i) {
            MinMax(mn, mx, &mn, &mx);
            A[i] = mn++;
            A[n-i+1] = mx--;
        }
        ll ans = 0;
        for (int i = 2; i <= n; ++i)
            ans = max(ans, A[i]-A[i-1]);
        return ans;
    } else {
        ll mn, mx;
        MinMax(0, 1e18, &mn, &mx);
        ll z = n-2 == 0 ? 0 : (mx-mn-1)/(n-2);
        vector<ll> num;
        num.push_back(mn);
        for (int i = 0; i < n-2; ++i) {
            ll l = mn+1 + z*i;
            ll r = mn+1 + z*(i+1) - 1;
            if (i == n-3) r = mx-1;
            ll mn2, mx2;
            MinMax(l, r, &mn2, &mx2);
            if (mn2 != -1) {
                num.push_back(mn2);
                num.push_back(mx2);
            }
        }
        num.push_back(mx);
        ll ans = 0;
        for (int i = 1; i < num.size(); ++i)
            ans = max(ans, num[i]-num[i-1]);
        return ans;
    }
}

Compilation message

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:41:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < num.size(); ++i)
                         ~~^~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	732 KB	Output is correct
3	Correct	2 ms	732 KB	Output is correct
4	Correct	2 ms	732 KB	Output is correct
5	Correct	2 ms	732 KB	Output is correct
6	Correct	2 ms	804 KB	Output is correct
7	Correct	2 ms	816 KB	Output is correct
8	Correct	2 ms	876 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	2 ms	876 KB	Output is correct
11	Correct	3 ms	888 KB	Output is correct
12	Correct	3 ms	916 KB	Output is correct
13	Correct	3 ms	960 KB	Output is correct
14	Correct	3 ms	1008 KB	Output is correct
15	Correct	3 ms	1060 KB	Output is correct
16	Correct	16 ms	1824 KB	Output is correct
17	Correct	16 ms	2316 KB	Output is correct
18	Correct	17 ms	2784 KB	Output is correct
19	Correct	16 ms	3372 KB	Output is correct
20	Correct	11 ms	3468 KB	Output is correct
21	Correct	58 ms	6440 KB	Output is correct
22	Correct	59 ms	8284 KB	Output is correct
23	Correct	59 ms	10384 KB	Output is correct
24	Correct	57 ms	11972 KB	Output is correct
25	Correct	48 ms	13176 KB	Output is correct
26	Correct	69 ms	15032 KB	Output is correct
27	Correct	60 ms	16876 KB	Output is correct
28	Correct	60 ms	18736 KB	Output is correct
29	Correct	61 ms	20580 KB	Output is correct
30	Correct	41 ms	21272 KB	Output is correct
31	Correct	2 ms	21272 KB	Output is correct
32	Correct	2 ms	21272 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	21272 KB	Output is correct
2	Correct	2 ms	21272 KB	Output is correct
3	Correct	2 ms	21272 KB	Output is correct
4	Correct	2 ms	21272 KB	Output is correct
5	Correct	2 ms	21272 KB	Output is correct
6	Correct	2 ms	21272 KB	Output is correct
7	Correct	2 ms	21272 KB	Output is correct
8	Correct	2 ms	21272 KB	Output is correct
9	Correct	2 ms	21272 KB	Output is correct
10	Correct	2 ms	21272 KB	Output is correct
11	Correct	3 ms	21272 KB	Output is correct
12	Correct	3 ms	21272 KB	Output is correct
13	Correct	3 ms	21272 KB	Output is correct
14	Correct	3 ms	21272 KB	Output is correct
15	Correct	3 ms	21272 KB	Output is correct
16	Correct	20 ms	21272 KB	Output is correct
17	Correct	21 ms	21448 KB	Output is correct
18	Correct	21 ms	22076 KB	Output is correct
19	Correct	21 ms	22392 KB	Output is correct
20	Correct	11 ms	22392 KB	Output is correct
21	Correct	80 ms	25708 KB	Output is correct
22	Correct	76 ms	27680 KB	Output is correct
23	Correct	84 ms	29392 KB	Output is correct
24	Correct	84 ms	31240 KB	Output is correct
25	Correct	77 ms	33480 KB	Output is correct
26	Correct	83 ms	34324 KB	Output is correct
27	Correct	80 ms	36160 KB	Output is correct
28	Correct	80 ms	38000 KB	Output is correct
29	Correct	80 ms	39848 KB	Output is correct
30	Correct	40 ms	39848 KB	Output is correct
31	Correct	2 ms	39848 KB	Output is correct
32	Correct	2 ms	39848 KB	Output is correct