답안 #106769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106769 2019-04-20T11:22:56 Z Diuven Gap (APIO16_gap) C++14
100 / 100
90 ms 4144 KB
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<lint, lint> pll;

pll ask(lint l, lint r){
	pll res;
//	cout<<"Ask: "<<l<<' '<<r<<'\n';
	MinMax(l, r, &res.first, &res.second);
	return res;
}

lint solve1(int n){
	vector<lint> A;
	lint s=1, e = 1e18;
	while((int)A.size()<n){
		pll now = ask(s,e);
		A.push_back(now.first);
		A.push_back(now.second);
		s = now.first+1, e = now.second-1;
	}
	sort(A.begin(), A.end());
	lint ans = 0;
	for(int i=1; i<(int)A.size(); i++) 
		ans = max(ans, A[i]-A[i-1]);
	return ans;
}

lint solve2(int n){
	pll F = ask(1, 1e18);
	lint s = F.first, e = F.second, l = (e-1)-(s+1)+1;
	lint b = l/n;
	vector<lint> V;
	for(int i=0; i<n; i++) V.push_back(b + (i<l-b*n));

	vector<pll> P;
	{
		lint now = s+1;
		for(int i=0; i<n; i++){
			if(V[i]<1){ P.push_back({-1,-1}); continue; }
			pll res = ask(now, now+V[i]-1);
			P.push_back(res);
			now += V[i];
		}
	}

	lint ans = 0;
	{
		lint last = s;
		for(int i=0; i<n; i++){
			if(P[i].first<0) continue;
			lint now = P[i].first - last;
			ans = max(ans, now);
			last = P[i].second;
		}
		ans = max(ans, e-last);
	}
	return ans;
}

lint findGap(int T, int N){
	if(T==1) return solve1(N);
	else return solve2(N);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 16 ms 896 KB Output is correct
17 Correct 16 ms 920 KB Output is correct
18 Correct 16 ms 1024 KB Output is correct
19 Correct 17 ms 896 KB Output is correct
20 Correct 13 ms 896 KB Output is correct
21 Correct 57 ms 2288 KB Output is correct
22 Correct 59 ms 2252 KB Output is correct
23 Correct 58 ms 2288 KB Output is correct
24 Correct 61 ms 2416 KB Output is correct
25 Correct 53 ms 2316 KB Output is correct
26 Correct 59 ms 2288 KB Output is correct
27 Correct 64 ms 2288 KB Output is correct
28 Correct 67 ms 2316 KB Output is correct
29 Correct 60 ms 2292 KB Output is correct
30 Correct 45 ms 2288 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 22 ms 1404 KB Output is correct
17 Correct 20 ms 1404 KB Output is correct
18 Correct 20 ms 1404 KB Output is correct
19 Correct 20 ms 1404 KB Output is correct
20 Correct 13 ms 1428 KB Output is correct
21 Correct 80 ms 4132 KB Output is correct
22 Correct 87 ms 4076 KB Output is correct
23 Correct 69 ms 4120 KB Output is correct
24 Correct 67 ms 4076 KB Output is correct
25 Correct 71 ms 4072 KB Output is correct
26 Correct 76 ms 4076 KB Output is correct
27 Correct 84 ms 4144 KB Output is correct
28 Correct 76 ms 4076 KB Output is correct
29 Correct 90 ms 4092 KB Output is correct
30 Correct 43 ms 4076 KB Output is correct
31 Correct 3 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct