답안 #708773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708773	2023-03-12T09:24:28 Z	hngwlog	Gap (APIO16_gap)	C++14	89.0375 / 100	1397 ms	9228 KB

gap

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

long long findGap(int t, int n) {

    vector<long long> a(n + 1);
    if (t == 1) {
        long long mi = - 1, ma = (long long)1e18 + 1;
        int l = 1;
        int r = n;
        while (l <= r) {
            MinMax(mi + 1, ma - 1, &mi, &ma);
            a[l] = mi, a[r] = ma;
            l++, r--;
        }
        long long ans = 0;
        for (int i = 2; i <= n; i++) ans = max(ans, a[i] - a[i - 1]);
        return ans;
    }
    long long ans = 0;
    long long mi = - 1, ma = (long long)1e18 + 1;
    MinMax(mi + 1, ma - 1, &mi, &ma);
    long long start = mi;
    long long maxx = ma;
    long long res = (ma - mi) / (n - 1);
    while (mi != maxx) {
        int cnt = 1;
        long long cur_mi = mi;
        long long fp = ((mi - start) / res + ((mi - start) % res ? 1 : 0)) * res + start + 1;
        cerr << "BEFORE: " << fp << " " << fp + res - 1 << '\n';
        MinMax(fp, fp + res - 1, &mi, &ma);
        cerr << mi << ' ' << ma << '\n' << '\n';
        while (mi == - 1) {
            cerr << "BEFORE: " << fp << " " << fp + res * (cnt + 1) - 1 << '\n';
            MinMax(fp, fp + res * (++cnt) - 1, &mi, &ma);
            cerr << mi << ' ' << ma << '\n' << '\n';
        }
        ans = max(ans, mi - cur_mi);
        mi = ma;
    }
    return ans;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	0 ms	208 KB	Output is correct
4	Correct	0 ms	208 KB	Output is correct
5	Correct	0 ms	208 KB	Output is correct
6	Correct	0 ms	208 KB	Output is correct
7	Correct	0 ms	208 KB	Output is correct
8	Correct	0 ms	208 KB	Output is correct
9	Correct	0 ms	208 KB	Output is correct
10	Correct	0 ms	208 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	10 ms	720 KB	Output is correct
17	Correct	13 ms	604 KB	Output is correct
18	Correct	9 ms	720 KB	Output is correct
19	Correct	12 ms	684 KB	Output is correct
20	Correct	7 ms	720 KB	Output is correct
21	Correct	41 ms	1836 KB	Output is correct
22	Correct	39 ms	1788 KB	Output is correct
23	Correct	38 ms	1824 KB	Output is correct
24	Correct	40 ms	1828 KB	Output is correct
25	Correct	32 ms	1884 KB	Output is correct
26	Correct	47 ms	1864 KB	Output is correct
27	Correct	36 ms	1772 KB	Output is correct
28	Correct	40 ms	1824 KB	Output is correct
29	Correct	39 ms	1812 KB	Output is correct
30	Correct	29 ms	1832 KB	Output is correct
31	Correct	0 ms	220 KB	Output is correct
32	Correct	0 ms	208 KB	Output is correct

Subtask #2

59.0374795838 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	0 ms	208 KB	Output is correct
6	Correct	2 ms	208 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	2 ms	336 KB	Output is correct
9	Correct	2 ms	336 KB	Output is correct
10	Correct	2 ms	208 KB	Output is correct
11	Correct	23 ms	336 KB	Output is correct
12	Correct	22 ms	372 KB	Output is correct
13	Correct	19 ms	432 KB	Output is correct
14	Correct	20 ms	336 KB	Output is correct
15	Correct	26 ms	376 KB	Output is correct
16	Correct	318 ms	2460 KB	Output is correct
17	Correct	327 ms	2500 KB	Output is correct
18	Correct	322 ms	2576 KB	Output is correct
19	Correct	324 ms	2520 KB	Output is correct
20	Partially correct	313 ms	1308 KB	Partially correct
21	Correct	1336 ms	9160 KB	Output is correct
22	Correct	1338 ms	9160 KB	Output is correct
23	Correct	1315 ms	9124 KB	Output is correct
24	Correct	1319 ms	9148 KB	Output is correct
25	Correct	1275 ms	7756 KB	Output is correct
26	Correct	1295 ms	9220 KB	Output is correct
27	Correct	1312 ms	9100 KB	Output is correct
28	Correct	1397 ms	9228 KB	Output is correct
29	Correct	1256 ms	9068 KB	Output is correct
30	Partially correct	1294 ms	4980 KB	Partially correct
31	Correct	2 ms	208 KB	Output is correct
32	Correct	3 ms	208 KB	Output is correct