제출 #793158

#제출 시각아이디문제언어결과실행 시간메모리
793158algorithm16Gap (APIO16_gap)C++14
70 / 100
75 ms5748 KiB
#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;*/ if(T==1) { llint x=1,y=1e18,r=0; while(x<y) { MinMax(x,y,&mn,&mx); if(mn==-1 && mx==-1) r=max(r,y-x); r=max(r,mn-x); r=max(r,y-mx); x=mn+1; y=mx-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; /*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:38:18: warning: unused variable 'rr' [-Wunused-variable]
   38 |  llint x=mn,y=mx,rr=mx-mn,r=(mx-mn)/(N-1)+((mx-mn)%(N-1)!=0);
      |                  ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...