Submission #80656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
80656	2018-10-22T00:45:50 Z	AngelKnows	Gap (APIO16_gap)	C++14	0 / 100	77 ms	39452 KB

gap

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

#define ll long long
ll mn,mx;
ll l,r,mid;
ll a[100005];
int h,t;
ll ans;
unsigned long long now,pre;
unsigned long long len;
long long findGap(int T, int N)
{
	if (T==1) {
		h=0,t=N+1;
		l=0,r=1e18+1;
		for (;;) {
			MinMax(l,r,&mn,&mx);
			a[++h]=mn,a[--t]=mx;
			l=mn+1,r=mx-1;
			if (h>=t-1) break;
		}
		for (int i=1;i<=N-1;i++) {
			ll t=a[i+1]-a[i];
			if (t>ans) ans=t;
		}
		printf("%lld\n",ans);
	} else {
		MinMax(0,1e18+1,&mn,&mx);
		now=mn;
		len=1;
		pre=now;
		while (now<=1e18) {
			MinMax(now+1,now+len,&mn,&mx);
			if (mn==-1) {
				now+=len;
				len*=2;
			} else {
				ans=max(ans,mn-(ll)pre);
				now=mx;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Subtask #1

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	504 KB	Expected EOF
2	Incorrect	2 ms	516 KB	Expected EOF
3	Incorrect	2 ms	692 KB	Expected EOF
4	Incorrect	2 ms	692 KB	Expected EOF
5	Incorrect	2 ms	692 KB	Expected EOF
6	Incorrect	2 ms	700 KB	Expected EOF
7	Incorrect	2 ms	808 KB	Expected EOF
8	Incorrect	2 ms	832 KB	Expected EOF
9	Incorrect	2 ms	836 KB	Expected EOF
10	Incorrect	2 ms	944 KB	Expected EOF
11	Incorrect	3 ms	944 KB	Expected EOF
12	Incorrect	3 ms	944 KB	Expected EOF
13	Incorrect	3 ms	944 KB	Expected EOF
14	Incorrect	3 ms	944 KB	Expected EOF
15	Incorrect	3 ms	1116 KB	Expected EOF
16	Incorrect	16 ms	1788 KB	Expected EOF
17	Incorrect	15 ms	2252 KB	Expected EOF
18	Incorrect	16 ms	2716 KB	Expected EOF
19	Incorrect	20 ms	3180 KB	Expected EOF
20	Incorrect	11 ms	3388 KB	Expected EOF
21	Incorrect	55 ms	6432 KB	Expected EOF
22	Incorrect	58 ms	8268 KB	Expected EOF
23	Incorrect	56 ms	10128 KB	Expected EOF
24	Incorrect	56 ms	12080 KB	Expected EOF
25	Incorrect	47 ms	13160 KB	Expected EOF
26	Incorrect	55 ms	15016 KB	Expected EOF
27	Incorrect	77 ms	16860 KB	Expected EOF
28	Incorrect	56 ms	18736 KB	Expected EOF
29	Incorrect	55 ms	20548 KB	Expected EOF
30	Incorrect	42 ms	21256 KB	Expected EOF
31	Incorrect	2 ms	21256 KB	Expected EOF
32	Incorrect	2 ms	21256 KB	Expected EOF

Subtask #2

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	21256 KB	Expected EOF
2	Incorrect	2 ms	21256 KB	Expected EOF
3	Incorrect	3 ms	21256 KB	Expected EOF
4	Incorrect	2 ms	21256 KB	Expected EOF
5	Incorrect	2 ms	21256 KB	Expected EOF
6	Incorrect	2 ms	21256 KB	Expected EOF
7	Incorrect	2 ms	21256 KB	Expected EOF
8	Incorrect	2 ms	21256 KB	Expected EOF
9	Incorrect	2 ms	21256 KB	Expected EOF
10	Incorrect	2 ms	21256 KB	Expected EOF
11	Incorrect	2 ms	21256 KB	Expected EOF
12	Incorrect	3 ms	21256 KB	Expected EOF
13	Incorrect	3 ms	21256 KB	Expected EOF
14	Incorrect	2 ms	21256 KB	Expected EOF
15	Incorrect	3 ms	21256 KB	Expected EOF
16	Incorrect	11 ms	21256 KB	Expected EOF
17	Incorrect	10 ms	21256 KB	Expected EOF
18	Incorrect	10 ms	21528 KB	Expected EOF
19	Incorrect	10 ms	22008 KB	Expected EOF
20	Incorrect	9 ms	22088 KB	Expected EOF
21	Incorrect	39 ms	24548 KB	Expected EOF
22	Incorrect	36 ms	26392 KB	Expected EOF
23	Incorrect	37 ms	28252 KB	Expected EOF
24	Incorrect	37 ms	30240 KB	Expected EOF
25	Incorrect	69 ms	31316 KB	Expected EOF
26	Incorrect	34 ms	33172 KB	Expected EOF
27	Incorrect	37 ms	35016 KB	Expected EOF
28	Incorrect	35 ms	36860 KB	Expected EOF
29	Incorrect	47 ms	38800 KB	Expected EOF
30	Incorrect	30 ms	39452 KB	Expected EOF
31	Incorrect	2 ms	39452 KB	Expected EOF
32	Incorrect	2 ms	39452 KB	Expected EOF