oj.uz

Submission #90003

# Submission time Handle Problem Language Result Execution time Memory
90003 2018-12-19T16:17:35 Z nikolapesic2802 The Big Prize (IOI17_prize) C++14
0 / 100
 144 ms 16072 KB 
#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=0)
    {
        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);
    }
    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;
        if(qs<=l&&qe>=r)
        {
            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);
        }
    }
};
int find_best(int n) {
    N=n;
    segTree tree;
    tree.initi();
    while(true)
    {
        //printf("1\n");
        int pos=tree.get_random_pos();
        //printf("2\n");
        vector<int> tr=ask(pos);
        int t=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);
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 15992 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 16072 KB Incorrect
2 Halted 0 ms 0 KB -