답안 #672452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
672452	2022-12-16T09:12:53 Z	Dan4Life	Gap (APIO16_gap)	C++17	100 / 100	55 ms	2244 KB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
const int maxn = 5e5+10;
const ll LINF = (ll)2e18;
 
ll ans=1,mn=-1,mx=-1;
 
ll findGap(int T, int n)
{
	ll s=0, t=LINF; ans=1;
	if(T==1){
		vector<ll> v; v.clear(); int x = (n+1)/2;
		while(x--) MinMax(s,t,&mn,&mx), v.pb(mn), v.pb(mx), s=mn+1, t=mx-1;
		sort(all(v));
		for(int i = 0; i < sz(v)-1; i++) 
			ans = max(ans, v[i+1]-v[i]);
		return ans;
	}
	MinMax(s,t,&mn,&mx); 
	ll x, y, i=mn, p=mn, num=(mx-mn+n-2)/(n-1); ans=num;
	for(; ; i+=num+1){
		MinMax(i,min(mx,i+num),&x,&y);
		if(x!=-1) ans = max(ans, x-p),p=y;
		if(i+num>=mx) break;
	}
	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	1 ms	208 KB	Output is correct
11	Correct	2 ms	336 KB	Output is correct
12	Correct	1 ms	340 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	816 KB	Output is correct
17	Correct	10 ms	848 KB	Output is correct
18	Correct	10 ms	812 KB	Output is correct
19	Correct	12 ms	848 KB	Output is correct
20	Correct	10 ms	804 KB	Output is correct
21	Correct	40 ms	2204 KB	Output is correct
22	Correct	39 ms	2240 KB	Output is correct
23	Correct	39 ms	2176 KB	Output is correct
24	Correct	39 ms	2196 KB	Output is correct
25	Correct	34 ms	2220 KB	Output is correct
26	Correct	38 ms	2244 KB	Output is correct
27	Correct	40 ms	2144 KB	Output is correct
28	Correct	41 ms	2240 KB	Output is correct
29	Correct	44 ms	2204 KB	Output is correct
30	Correct	33 ms	2200 KB	Output is correct
31	Correct	0 ms	208 KB	Output is correct
32	Correct	0 ms	208 KB	Output is correct

Subtask #2

70.0 / 70.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	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	0 ms	208 KB	Output is correct
7	Correct	1 ms	208 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	208 KB	Output is correct
11	Correct	1 ms	208 KB	Output is correct
12	Correct	1 ms	208 KB	Output is correct
13	Correct	1 ms	208 KB	Output is correct
14	Correct	1 ms	208 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	15 ms	500 KB	Output is correct
17	Correct	12 ms	556 KB	Output is correct
18	Correct	12 ms	504 KB	Output is correct
19	Correct	14 ms	464 KB	Output is correct
20	Correct	6 ms	464 KB	Output is correct
21	Correct	52 ms	1056 KB	Output is correct
22	Correct	55 ms	1076 KB	Output is correct
23	Correct	50 ms	1080 KB	Output is correct
24	Correct	54 ms	1088 KB	Output is correct
25	Correct	46 ms	968 KB	Output is correct
26	Correct	50 ms	1076 KB	Output is correct
27	Correct	48 ms	1060 KB	Output is correct
28	Correct	48 ms	1080 KB	Output is correct
29	Correct	49 ms	1080 KB	Output is correct
30	Correct	24 ms	976 KB	Output is correct
31	Correct	0 ms	208 KB	Output is correct
32	Correct	1 ms	208 KB	Output is correct