#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int N;
struct segTree{
vector<double> lazy;
vector<double> maxx;
vector<int> num;
vector<int> poss;
void prop(int i)
{
if(lazy[i]==1)
return;
lazy[2*i]*=lazy[i];
lazy[2*i+1]*=lazy[i];
maxx[2*i]*=lazy[i];
maxx[2*i+1]*=lazy[i];
if(maxx[2*i]==0)
poss[2*i]=0;
if(maxx[2*i+1]==0)
poss[2*i+1]=0;
lazy[i]=1;
}
void update(int i)
{
poss[i]=poss[2*i]+poss[2*i+1];
if(maxx[2*i]>maxx[2*i+1])
{
maxx[i]=maxx[2*i];
num[i]=num[2*i];
}
if(maxx[2*i]<maxx[2*i+1])
{
maxx[i]=maxx[2*i+1];
num[i]=num[2*i+1];
}
if(maxx[2*i]==maxx[2*i+1])
{
maxx[i]=maxx[2*i];
num[i]=num[2*i]+num[2*i+1];
}
}
void init(int l=0,int r=N-1,int i=1)
{
lazy[i]=1;
if(l==r){
maxx[i]=1,num[i]=1,poss[i]=1;
return;
}
int m=(l+r)>>1;
init(l,m,2*i);
init(m+1,r,2*i+1);
update(i);
//printf("%i-%i %i %f %i\n",l,r,i,maxx[i],num[i]);
}
void initi()
{
lazy.resize(4*N);
maxx.resize(4*N);
poss.resize(4*N);
num.resize(4*N);
init();
}
void add(int qs,int qe,double what,int l=0,int r=N-1,int i=1)
{
if(qs>r||qe<l)
return;
//printf("Addujem %i %i %f %i %i %i\n",qs,qe,what,l,r,i);
if(qs<=l&&qe>=r)
{
//printf("Usao!\n");
lazy[i]*=what;
maxx[i]*=what;
if(maxx[i]==0)
poss[i]=0;
return;
}
prop(i);
int m=(l+r)>>1;
add(qs,qe,what,l,m,2*i);
add(qs,qe,what,m+1,r,2*i+1);
update(i);
}
int get_random_pos(int l=0,int r=N-1,int i=1)
{
//printf("%i %i %i\n",l,r,i);
if(l==r)
return l;
prop(i);
int m=(l+r)>>1;
if(maxx[2*i]==maxx[2*i+1])
{
//printf("ISTO! %i\n",m);
int d=r-l+1,num1=num[2*i],num2=num[2*i+1];
double s1=(double)num1/d,s2=(double)num2/d;
double s=s1+s2;
double lim=(double)s1/s;
double ra=(double)rand()/RAND_MAX;
if(ra<=lim)
return get_random_pos(l,m,2*i);
else
return get_random_pos(m+1,r,2*i+1);
}
else
{
if(maxx[2*i]>maxx[2*i+1])
return get_random_pos(l,m,2*i);
else
return get_random_pos(m+1,r,2*i+1);
}
}
void print()
{
printf("Vrednosti:\n");
printt();
printf("\n");
}
void printt(int l=0,int r=N-1,int i=1)
{
if(l==r)
{
printf("%.2f ",maxx[i]);
return;
}
prop(i);
int m=(l+r)>>1;
printt(l,m,2*i);
printt(m+1,r,2*i+1);
}
};
int find_best(int n) {
int limm=1e4;
N=n;
segTree tree;
tree.initi();
//tree.print();
while(true)
{
//printf("1\n");
int pos=tree.get_random_pos();
limm--;
if(limm<0)
assert(0);
//printf("Uzimam random: %i\n",pos);
//printf("2\n");
vector<int> tr=ask(pos);
int t=tr[0]+tr[1];
//printf("%i %i\n",tr[0],tr[1]);
if(t==0)
return pos;
int d=n-1;
//tree.print();
double s1=(double)tr[0]/d,s2=(double)tr[1]/d;
double s=s1+s2;
double lim=(double)s1/s;
tree.add(pos,pos,0);
tree.add(0,pos-1,(double)lim);
tree.add(pos+1,n-1,(double)1-lim);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
19064 KB |
Output is correct |
| 2 |
Correct |
23 ms |
19268 KB |
Output is correct |
| 3 |
Correct |
22 ms |
19268 KB |
Output is correct |
| 4 |
Correct |
23 ms |
19272 KB |
Output is correct |
| 5 |
Correct |
22 ms |
19272 KB |
Output is correct |
| 6 |
Correct |
26 ms |
19292 KB |
Output is correct |
| 7 |
Correct |
23 ms |
19324 KB |
Output is correct |
| 8 |
Correct |
23 ms |
19324 KB |
Output is correct |
| 9 |
Correct |
23 ms |
19356 KB |
Output is correct |
| 10 |
Correct |
24 ms |
19356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
19356 KB |
Output is correct |
| 2 |
Correct |
22 ms |
19356 KB |
Output is correct |
| 3 |
Correct |
23 ms |
19356 KB |
Output is correct |
| 4 |
Correct |
22 ms |
19356 KB |
Output is correct |
| 5 |
Correct |
22 ms |
19372 KB |
Output is correct |
| 6 |
Correct |
24 ms |
19372 KB |
Output is correct |
| 7 |
Correct |
23 ms |
19372 KB |
Output is correct |
| 8 |
Correct |
23 ms |
19372 KB |
Output is correct |
| 9 |
Correct |
24 ms |
19372 KB |
Output is correct |
| 10 |
Correct |
24 ms |
19372 KB |
Output is correct |
| 11 |
Runtime error |
175 ms |
38312 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
