#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int N;
struct segTree{
vector<double> lazy;
vector<double> maxx;
vector<int> num;
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];
lazy[i]=1;
}
void update(int i)
{
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;
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);
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;
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) {
N=n;
segTree tree;
tree.initi();
//tree.print();
while(true)
{
//printf("1\n");
int pos=tree.get_random_pos();
//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;
tree.add(pos,pos,0);
tree.add(0,pos-1,(double)tr[0]/t);
tree.add(pos+1,n-1,(double)tr[1]/t);
//tree.print();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
20 ms |
15948 KB |
Token "Addujem" doesn't correspond to pattern "[A-B]{1}" |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
16096 KB |
Token "Addujem" doesn't correspond to pattern "[A-B]{1}" |
2 |
Halted |
0 ms |
0 KB |
- |