Submission #48981

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48981	2018-05-21T06:01:45 Z	Namnamseo	Gap (APIO16_gap)	C++17	100 / 100	197 ms	39436 KB

gap

#include "gap.h"
#include <algorithm>
using namespace std;

typedef long long ll;

ll big=ll(1e18);

int n;

ll binwork(ll X, ll Y,int n){
	ll a,b;
	MinMax(X, Y, &a, &b);
	if(n==2) return b-a;
	ll ans=0;
	n-=2;
	while(true){
		ll c,d;
		MinMax(a+1, b-1, &c, &d);
		ans=max({ans, c-a, b-d});
		if(n==1){
			break;
		}
		if(n==2){
			ans=max(ans, d-c);
			break;
		}
		n-=2;
		a=c; b=d;
	}
	return ans;
}

ll work2(){
	ll x,y;
	MinMax(0,big,&x,&y);
	ll l=x+1, r=y-1;
	ll width = (r-l+1)/n;
	int i;
	ll li=l;
	ll lastp = x;
	ll ans=0;
	for(i=0; i<n; ++i){
		ll p=li, q=li+width-1;
		if( i < (r-l+1)-width*n ) ++q;
		li=q+1;
		ll ba, bb;
		MinMax(p, q, &ba, &bb);
		if(ba!=-1){
			ans=max(ans, ba-lastp);
			lastp=bb;
		}
	}
	ans=max(ans, y-lastp);
	return ans;
}

ll findGap(int T, int N)
{
	if(T == 1){
		return binwork(0, big, N);
	} else {
		if(N==2){
			ll a,b;
			MinMax(0, big, &a, &b);
			return b-a;
		}
		n=N;
		return work2();
	}
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	2 ms	528 KB	Output is correct
4	Correct	3 ms	528 KB	Output is correct
5	Correct	2 ms	552 KB	Output is correct
6	Correct	2 ms	552 KB	Output is correct
7	Correct	2 ms	552 KB	Output is correct
8	Correct	2 ms	552 KB	Output is correct
9	Correct	2 ms	552 KB	Output is correct
10	Correct	2 ms	624 KB	Output is correct
11	Correct	3 ms	720 KB	Output is correct
12	Correct	3 ms	764 KB	Output is correct
13	Correct	4 ms	864 KB	Output is correct
14	Correct	4 ms	908 KB	Output is correct
15	Correct	3 ms	936 KB	Output is correct
16	Correct	18 ms	1592 KB	Output is correct
17	Correct	17 ms	2184 KB	Output is correct
18	Correct	16 ms	2632 KB	Output is correct
19	Correct	17 ms	3072 KB	Output is correct
20	Correct	14 ms	3188 KB	Output is correct
21	Correct	69 ms	5776 KB	Output is correct
22	Correct	58 ms	7492 KB	Output is correct
23	Correct	85 ms	9464 KB	Output is correct
24	Correct	71 ms	11180 KB	Output is correct
25	Correct	55 ms	12384 KB	Output is correct
26	Correct	61 ms	14240 KB	Output is correct
27	Correct	62 ms	16100 KB	Output is correct
28	Correct	65 ms	17944 KB	Output is correct
29	Correct	60 ms	19792 KB	Output is correct
30	Correct	43 ms	20420 KB	Output is correct
31	Correct	2 ms	20420 KB	Output is correct
32	Correct	3 ms	20420 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	20420 KB	Output is correct
2	Correct	2 ms	20420 KB	Output is correct
3	Correct	3 ms	20420 KB	Output is correct
4	Correct	2 ms	20420 KB	Output is correct
5	Correct	2 ms	20420 KB	Output is correct
6	Correct	2 ms	20420 KB	Output is correct
7	Correct	2 ms	20420 KB	Output is correct
8	Correct	2 ms	20420 KB	Output is correct
9	Correct	2 ms	20420 KB	Output is correct
10	Correct	2 ms	20420 KB	Output is correct
11	Correct	4 ms	20420 KB	Output is correct
12	Correct	4 ms	20420 KB	Output is correct
13	Correct	3 ms	20420 KB	Output is correct
14	Correct	4 ms	20420 KB	Output is correct
15	Correct	4 ms	20420 KB	Output is correct
16	Correct	20 ms	20588 KB	Output is correct
17	Correct	24 ms	21172 KB	Output is correct
18	Correct	23 ms	21648 KB	Output is correct
19	Correct	29 ms	22004 KB	Output is correct
20	Correct	10 ms	22076 KB	Output is correct
21	Correct	89 ms	24584 KB	Output is correct
22	Correct	138 ms	26572 KB	Output is correct
23	Correct	78 ms	28236 KB	Output is correct
24	Correct	78 ms	30152 KB	Output is correct
25	Correct	72 ms	31308 KB	Output is correct
26	Correct	79 ms	33328 KB	Output is correct
27	Correct	197 ms	35040 KB	Output is correct
28	Correct	91 ms	37036 KB	Output is correct
29	Correct	77 ms	38868 KB	Output is correct
30	Correct	42 ms	39436 KB	Output is correct
31	Correct	3 ms	39436 KB	Output is correct
32	Correct	3 ms	39436 KB	Output is correct