Submission #263377

#	Time	Username	Problem	Language	Result	Execution time	Memory
263377		Coroian_David	The Big Prize (IOI17_prize)	C++11	20 / 100	72 ms	4344 KiB

prize

#include <bits/stdc++.h>

//#include "prize.h"

#define MAX_N 200000

#define xx first
#define yy second

using namespace std;

typedef long long lint;

vector<int> ask(int i);

int N;
int mx;
int rez = -1;
int spec[MAX_N + 1];

int xd[MAX_N + 1];
pair <int, int> q[MAX_N + 1];

vector <int> tmp;

int ST, DR;

int aib[MAX_N + 1];

void baga(int poz, int nr)
{
    while(poz <= N)
    {
        aib[poz] += nr;
        poz += poz & (-poz);
    }
}

int getSum(int poz)
{
    int rez = 0;
    while(poz > 0)
    {
        rez += aib[poz];
        poz -= poz & (-poz);
    }

    return rez;
}

int getS(int st, int dr)
{
    int rez = getSum(dr);
    rez -= getSum(st - 1);

    return rez;
}

vector <int> doAsk(int poz)
{
    static int CNT = 0;

    if(rez != -1)
        return {0, 0};

    if(xd[poz] == 1)
    {
        tmp[0] = q[poz].xx;
        tmp[1] = q[poz].yy;

        return tmp;
    }

    xd[poz] = 1;


    CNT ++;

    assert(CNT <= 5000);
    vector <int> a = ask(poz - 1);
    q[poz] = {a[0], a[1]};

    if(a[0] + a[1] == 0)
        rez = poz;

    else if(a[0] + a[1] < mx)
    {
        spec[poz] = 1;
        baga(poz, 1);

        if(a[0] == 0)
            ST = max(ST, poz);

        if(a[1] == 0)
            DR = min(DR, poz);
    }


    return a;
}

bool verif(int poz, int &cst, int &cdr, int &px)
{
    if(rez != -1)
        return 0;

    vector <int> a = doAsk(poz);

    if(a[0] + a[1] == mx)
    {
        cst = a[0];
        cdr = a[1];
        px = poz;

        return 1;
    }

    spec[poz] = 1;
    return 0;
}

void intreaba(int poz, int &cst, int &cdr, int &px)
{
    int n = N;

    if(rez != -1)
        return;

    if(verif(poz, cst, cdr, px))
        return;

    int st = poz - 1;
    int dr = poz + 1;
    while(st >= 1 || dr <= n)
    {
        if(st >= 1)
        {
            if(verif(st, cst, cdr, px))
                return;

            st --;
        }

        if(dr <= n)
        {
            if(verif(dr, cst, cdr, px))
                return;

            dr ++;
        }
    }
}

void divide(int st, int dr, int pst, int pdr, int cate)
{
    if(rez != -1)
        return;

    st = max(st, ST);
    dr = min(dr, DR);

    if(st > dr || cate == 0)
        return;

    int nou = cate - getS(st, dr);
    if(nou <= 0)
        return;

   // cout << " SUNTEM " << st << " " << dr << " AVEM INSRE ST " << pst << " DR " << pdr << " " << cate << "\n";

    if((dr - st + 1) - cate <= 1)
    {
        for(int i = st; i <= dr; i ++)
            doAsk(i);

        return;
    }


    int cst, cdr, px;
    int mid = (st + dr) >> 1;
    intreaba(mid, cst, cdr, px);

    divide(st, px - 1, pst, cdr, cst - pst);
    divide(px + 1, dr, cst, pdr, cdr - pdr);
}

int find_best(int n)
{
    ST = 1;
    DR = n;
    N = n;
    tmp.resize(2);
    if(n <= 5000)
    {
        for(int i = 0; i < n; i ++)
        {
            vector<int> a = ask(i);

            if(a[0] + a[1] == 0)
                return i;
        }

        assert(1 == 0);
        //return;
    }

    srand(time(0));
    for(int i = 1; i <= 20; i ++)
    {
        lint poz = 1LL * rand() * rand() % n;

        vector <int> a = doAsk(poz + 1);

        if(a[0] + a[1] == 0)
            return poz;

        mx = max(mx, a[0] + a[1]);
    }

    divide(1, n, 0, 0, mx);

    return rez - 1;
}

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