이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
/*cout << 1 << " " << 1e18 << "\n";
cin >> mn >> mx;*/
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;
/*cout << x << " " << x+mid << "\n";
cin >> mn >> mx;*/
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,5);
return 0;
}*/
컴파일 시 표준 에러 (stderr) 메시지
gap.cpp: In function 'llint findGap(int, int)':
gap.cpp:26:18: warning: unused variable 'rr' [-Wunused-variable]
26 | llint x=mn,y=mx,rr=mx-mn,r=(mx-mn)/(N-1)+((mx-mn)%(N-1)!=0);
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |