이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#include "prize.h"
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>
using namespace std;
const int MAXN = 2e5 + 1;
const ll INF = 1e17;
bool sp[MAXN];
int ans = -1;
int brute(int n){
FOR(i,n){
vi a = ask(i);
if(a[0] == 0 and a[1] == 0)return i;
}
}
int mx = 0;
void binsrch(int l,int r,int sp_left,int sp_right){
if(l > r)return;
if(ans != -1)return;
if(sp_right + sp_left == mx)return;
int mid = (l+r)/2;
vi a = ask(mid);
if(a[0] + a[1] == mx){
// this is a lollipop;
binsrch(l,mid-1,sp_left,a[1]);
binsrch(mid+1,r,a[0],sp_right);
}else{
// now we extend the pointers to both directions to find the closest lollipops
if(a[0] + a[1] == 0){
ans = mid;
return;
}
int rptr = mid+1;
vi a1;
while(rptr <= r){
a1 = ask(rptr);
if(a1[0] + a1[1] == 0){
ans = rptr;
return;
}else if(a1[0] + a1[1] == mx){
binsrch(rptr+1,r,a1[0],sp_right);
binsrch(l,mid-1,sp_left,a1[1] + (rptr-mid));
return;
}else{
rptr++;
}
}
binsrch(l,mid-1,sp_left,(r-mid+1) + a[1]);
return;
return;
int lptr = mid-1;
while(lptr >= l){
a1 = ask(lptr);
if(a1[0] + a1[1] == 0){
ans = lptr;
return;
}else if(a1[0] + a1[1] == mx){
binsrch(l,lptr-1,sp_left,a1[1]);
break;
}else{
lptr--;
}
}
}
}
int find_best(int n){
if(n <= 5000)return brute(n);
FOR(i,500){
vi a = ask(i);
if(a[0] + a[1] == 0){
return i;
}
if(a[0] + a[1] > 500){
mx = a[0] + a[1];
binsrch(i+1,n-1,i,0);
return ans;
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
prize.cpp: In function 'int brute(int)':
prize.cpp:31:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |