#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int i,j,n,m,ll,rr,xl,xr,last,rez,mas[200005][2];
vector<int> aa;
int bins(int sum,int l,int r)
{
ll=0;
rr=n-1;
int c=l+(r-l)/2;
while (l<r)
{
int c2=0;
aa=ask(c);
xl=aa[0];
xr=aa[1];
mas[c][0]=xl;
mas[c][1]=xr;
if (xl+xr<=sum)
{
return c;
}
if (xl>0)
{
r=c-1;
c2=bins(xl+xr,l,r);
if (mas[c2][0]+mas[c2][1]<=sum)
{
return c2;
}
if (mas[c2][0]+mas[c2][1]<mas[c][0]+mas[c][1])
{
l=0;
r=n-1;
c=c2;
}
else if (mas[c2][0]!=mas[c][0])
{
l=c2+1;
c=l+(r-l)/2;
}
else
{
r=c2-1;
c=l+(r-l)/2;
}
}
else
{
l=c+1;
c2=bins(xl+xr,l,r);
if (mas[c2][0]+mas[c2][1]<=sum)
{
return c2;
}
if (mas[c2][0]+mas[c2][1]<mas[c][0]+mas[c][1])
{
l=0;
r=n-1;
c=c2;
}
else if (mas[c2][1]!=mas[c][1])
{
r=c2-1;
c=l+(r-l)/2;
}
else
{
l=c2+1;
c=l+(r-l)/2;
}
}
}
}
int find_best(int n)
{
return bins(0,0,n-1);
}
Compilation message
prize.cpp: In function 'int bins(int, int, int)':
prize.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
304 KB |
Output is correct |
2 |
Correct |
4 ms |
440 KB |
Output is correct |
3 |
Correct |
3 ms |
440 KB |
Output is correct |
4 |
Correct |
3 ms |
464 KB |
Output is correct |
5 |
Correct |
2 ms |
476 KB |
Output is correct |
6 |
Correct |
3 ms |
528 KB |
Output is correct |
7 |
Correct |
3 ms |
572 KB |
Output is correct |
8 |
Correct |
3 ms |
572 KB |
Output is correct |
9 |
Correct |
3 ms |
572 KB |
Output is correct |
10 |
Correct |
3 ms |
572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
572 KB |
Output is correct |
2 |
Correct |
2 ms |
580 KB |
Output is correct |
3 |
Correct |
3 ms |
580 KB |
Output is correct |
4 |
Correct |
3 ms |
580 KB |
Output is correct |
5 |
Correct |
3 ms |
580 KB |
Output is correct |
6 |
Correct |
3 ms |
580 KB |
Output is correct |
7 |
Correct |
3 ms |
580 KB |
Output is correct |
8 |
Correct |
3 ms |
580 KB |
Output is correct |
9 |
Correct |
2 ms |
580 KB |
Output is correct |
10 |
Correct |
3 ms |
580 KB |
Output is correct |
11 |
Incorrect |
3 ms |
580 KB |
answer is not correct |
12 |
Halted |
0 ms |
0 KB |
- |