제출 #1238478

#제출 시각아이디문제언어결과실행 시간메모리
1238478vivkostovThe Big Prize (IOI17_prize)C++20
20 / 100
24 ms424 KiB
//#pragma once //#include "grader.cpp" #include "prize.h" #include <bits/stdc++.h> using namespace std; mt19937 mt(time(nullptr)); int sum,lamp,n,num=10,lf,rf,rr,used[200005]; void prec() { vector<int>a; int h; for(int i=1; i<=10; i++) { h=mt()%n; a=(ask(h)); sum=max(sum,a[0]+a[1]); } } void rec(int l,int r,int br,int exl,int exr) { if(lamp)return; if(br==0)rr++; int mid=(l+r)/2,ad=1; vector<int>a; while(true) { if(num>=9998) { lamp=rr+20000000; return; } a=ask(mid-1); num++; if(a[0]+a[1]==0) { lamp=mid; return; } if(a[0]==0)lf=mid+1; if(a[1]==0)rf=mid-1; if(a[0]+a[1]==sum) { break; } mid+=ad; if(mid>r) { mid=(l+r)/2-1; ad=-1; } if(mid<l)return; } int dist=abs(mid-(l+r)/2); if(mid>=(l+r)/2) { //if(a[1]-exr>0&&a[0]-exl-dist>0)rr++; if(a[1]-exr>0)rec(mid+1,r,a[1]-exr,a[0],exr); if(a[0]-exl-dist>0)rec(l,(l+r)/2-1,a[0]-exl-dist,exl,a[1]+dist); } else { if(a[0]-exl>0)rec(l,mid-1,a[0]-exl,exl,a[1]); } } int find_best(int N) { n=N; rf=N; prec(); rec(1,n,sum,0,0); return lamp-1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...