Submission #90005

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
90005	2018-12-19T16:33:26 Z	nikolapesic2802	The Big Prize (IOI17_prize)	C++14	20 / 100	84 ms	16296 KB

prize

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

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	15992 KB	Output is correct
2	Correct	19 ms	15992 KB	Output is correct
3	Correct	19 ms	15992 KB	Output is correct
4	Correct	19 ms	16164 KB	Output is correct
5	Correct	18 ms	16164 KB	Output is correct
6	Correct	19 ms	16164 KB	Output is correct
7	Correct	19 ms	16164 KB	Output is correct
8	Correct	19 ms	16164 KB	Output is correct
9	Correct	18 ms	16172 KB	Output is correct
10	Correct	19 ms	16188 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	16240 KB	Output is correct
2	Correct	18 ms	16244 KB	Output is correct
3	Correct	16 ms	16244 KB	Output is correct
4	Correct	18 ms	16244 KB	Output is correct
5	Correct	18 ms	16244 KB	Output is correct
6	Correct	19 ms	16296 KB	Output is correct
7	Correct	17 ms	16296 KB	Output is correct
8	Correct	19 ms	16296 KB	Output is correct
9	Correct	18 ms	16296 KB	Output is correct
10	Correct	19 ms	16296 KB	Output is correct
11	Incorrect	84 ms	16296 KB	Incorrect
12	Halted	0 ms	0 KB	-