oj.uz

답안 #394411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394411 2021-04-26T14:05:41 Z jsannemo Gap (APIO16_gap) C++14
100 / 100
 75 ms 2372 KB 
#include "gap.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<ll> qs;

pair<ll, ll> query(ll lo, ll hi) {
	pair<ll, ll> res;
	MinMax(lo, hi, &res.first, &res.second);
	/// cerr << "q " << lo << " " << hi << endl;
	if (res.first != -1) {
		qs.push_back(res.first);
		if (res.first != res.second) qs.push_back(res.second);
	}
	return res;
}

long long findGap(int T, int N) {
	if (T == 1) {
		ll lo = 0;
		ll hi = 1'000'000'000'000'000'000;
		for (int i = 0; i < (N + 1) / 2 && lo <= hi; ++i) {
			tie(lo, hi) = query(lo, hi);
			++lo; --hi;
		}
	}
	if (T == 2) {
		ll lo = 0;
		ll hi = 1'000'000'000'000'000'000;
		tie(lo, hi) = query(lo, hi);
		++lo;
		--hi;
		for (int k = N - 1; k >= 1; --k) {
			ll nask = lo + (hi - lo) / k;
			query(lo, nask);
			lo = nask + 1;
		}
	}
	sort(all(qs));
	ll res = 0;
	rep(i,0,sz(qs) - 1) res = max(res, qs[i + 1] - qs[i]);
	return res;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 12 ms 840 KB Output is correct
17 Correct 12 ms 844 KB Output is correct
18 Correct 14 ms 840 KB Output is correct
19 Correct 12 ms 840 KB Output is correct
20 Correct 10 ms 840 KB Output is correct
21 Correct 49 ms 2276 KB Output is correct
22 Correct 49 ms 2136 KB Output is correct
23 Correct 52 ms 2200 KB Output is correct
24 Correct 49 ms 2196 KB Output is correct
25 Correct 44 ms 2168 KB Output is correct
26 Correct 50 ms 2372 KB Output is correct
27 Correct 48 ms 2280 KB Output is correct
28 Correct 61 ms 2136 KB Output is correct
29 Correct 49 ms 2128 KB Output is correct
30 Correct 43 ms 2208 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 1 ms 200 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 18 ms 940 KB Output is correct
17 Correct 18 ms 872 KB Output is correct
18 Correct 21 ms 872 KB Output is correct
19 Correct 15 ms 860 KB Output is correct
20 Correct 8 ms 460 KB Output is correct
21 Correct 62 ms 2136 KB Output is correct
22 Correct 62 ms 2124 KB Output is correct
23 Correct 65 ms 2128 KB Output is correct
24 Correct 64 ms 2164 KB Output is correct
25 Correct 58 ms 2196 KB Output is correct
26 Correct 66 ms 2232 KB Output is correct
27 Correct 75 ms 2292 KB Output is correct
28 Correct 64 ms 2196 KB Output is correct
29 Correct 71 ms 2228 KB Output is correct
30 Correct 35 ms 1524 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 1 ms 200 KB Output is correct