제출 #793168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793168		algorithm16	Gap (APIO16_gap)	C++14	70 / 100	69 ms	5652 KiB

gap

#include "gap.h"
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
typedef long long int llint;
set <llint> s;
llint fnd(llint x,llint r) {
	set <llint>::iterator it=s.upper_bound(x+r);
	if(it!=s.begin()) {
		it--;
		if((*it)!=x) return (*it);
	}
	llint mn=0,mx=0;
	MinMax(x+1,x+r,&mn,&mx);
	s.insert(mn);
	s.insert(mx);
	return mx;
}
llint findGap(int T, int N)
{
	llint mn,mx;
	if(T==1) {
		llint x=1,y=1e18,r=0,cnt=0;
		while(x<y) {
			MinMax(x,y,&mn,&mx);
			//cout << x << " " << y << "\n";
			//cin >> mn >> mx;
			if(mn==-1 && mx==-1) {
				r=max(r,y-x+2);
				break;
			}
			if(cnt) r=max(r,mn-x+1);
			if(cnt) r=max(r,y-mx+1);
			//cout << r << "\n";
			x=mn+1;
			y=mx-1;
			cnt+=1;
		}
		return r;
	}
	MinMax(1LL,(llint)1e18,&mn,&mx);
	llint x=mn,y=mx,rr=mx-mn,r=(mx-mn)/(N-1)+((mx-mn)%(N-1)!=0);
	s.insert(mn);
	s.insert(mx);
	while(x!=y) {
		llint x1=fnd(x,r);
		if(x1!=-1) {
			x=x1;
			continue;
		}
		llint lo=r,hi=min(y-x,r*4);
		while(lo<hi) {
			llint mid=(lo+hi)/2;
			llint x1=fnd(x,mid);
			if(x1!=-1) {
				lo=(*s.lower_bound(x+1))-x;
				break;
			}
			else lo=mid+1;
		}
		if(lo<min(y-x,r*4)) x+=lo;
		r=lo;
	}
	return r;
}
/*int main()
{
	cout << findGap(1,6);
	return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

gap.cpp: In function 'llint findGap(int, int)':
gap.cpp:43:18: warning: unused variable 'rr' [-Wunused-variable]
   43 |  llint x=mn,y=mx,rr=mx-mn,r=(mx-mn)/(N-1)+((mx-mn)%(N-1)!=0);
      |                  ^~

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