Submission #90009

#	Time	Username	Problem	Language	Result	Execution time	Memory
90009		nikolapesic2802	The Big Prize (IOI17_prize)	C++14	20 / 100	175 ms	38312 KiB

prize

#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);
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80