Submission #42637

#	Time	Username	Problem	Language	Result	Execution time	Memory
42637		fefe	Gap (APIO16_gap)	C++14	0 / 100	105 ms	3824 KiB

gap

#include "gap.h"
#include<stack>
#define f MinMax
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
long long findGap(int T, int N)
{
	long long s,e,ps,pe,maxx=0,x,y;
	if(T==1){
		f(0,(1LL<<62),&ps,&pe);
		N-=2;
		while(N>=2){
			f(ps+1,pe-1,&s,&e);
			N-=2;
			maxx=max(maxx,max(s-ps,pe-e));
			ps=s;pe=e;
		}
		return max(maxx,pe-ps);
	}
	f(0,(1LL<<62),&ps,&pe);
	x=0;
	struct node{
		long long x,s,e;
	};
	stack<node> st;
	node p;
	while(ps!=pe){
		y=x;
		while(1){
			f(ps+1,ps+(1LL<<y),&s,&e);
			if(s!=-1)	break;
			y++;
		}
		if(x!=y)	while(!st.empty())	st.pop();
		p.x=ps;p.s=s;p.e=e;
		st.push(p);
		x=y;
		ps=e;
	}
	if(x==0)	return 1;
	while(!st.empty()){
		p=st.top();st.pop();
		f(p.x+1,p.x+(1LL<<(x-1)),&s,&e);
		if(s!=-1)	continue;
		maxx=max(maxx,p.s-p.x);
	}
	return maxx;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70