Submission #1019761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019761		andrei_iorgulescu	The Big Prize (IOI17_prize)	C++17	95.54 / 100	41 ms	6480 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> f[200005];
bool viz[200005];

vector<int> askk(int pos)
{
    if (viz[pos])
        return f[pos];
    viz[pos] = true;
    f[pos] = ask(pos - 1);
    return f[pos];
}

/*
8
3 2 3 1 3 3 2 3
*/

int aib[200005];

void update(int pos)
{
    for (int i = pos; i <= 200000; i += (i & -i))
        aib[i]++;
}

int query(int pos)
{
    int rr = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        rr += aib[i];
    return rr;
}

int find_best(int n)
{
    int sn = 500;
    sn = min(sn,n);
    int nrmax = 0,ret_sc;
    int seen = 0;
    for (int i = 1; i <= sn; i++)
    {
        vector<int> cur = askk(i);
        if (cur[0] + cur[1] == 0)
            return i - 1;
        nrmax = max(nrmax,cur[0] + cur[1]);
        if (cur[0] + cur[1] == nrmax)
            ret_sc = cur[1];
    }
    for (int i = 1; i <= sn; i++)
        if (askk(i)[0] + askk(i)[1] < nrmax)
            update(i);
    int cate = nrmax;
    set<int> pozi;
    int p = sn + 1;
    while (true)
    {
        int st = p;
        int dr;
        if (pozi.empty() or ((*pozi.rbegin()) < p))
            dr = n;
        else
            dr = *pozi.lower_bound(st);
        int dr0 = dr;
        dr = min(dr,st + (n - st) / (cate - query(st)));
        if (dr != dr0)
        {
            vector<int> lol = askk(dr);
            if (lol[0] + lol[1] == nrmax and lol[1] == ret_sc)
            {
                p = dr + 1;
                continue;
            }
        }
        while (st < dr)
        {
            int mij = (st + dr) / 2;
            vector<int> cur = askk(mij);
            if (cur[0] + cur[1] < nrmax)
            {
                if (query(mij) - query(mij - 1) == 0)
                    update(mij);
                pozi.insert(mij);
                dr = mij;
            }
            else
            {
                if (cur[1] == ret_sc)
                    st = mij + 1;
                else
                    dr = mij;
            }
        }
        while (true)
        {
            vector<int> cur = askk(st);
            if (cur[0] + cur[1] == 0)
                return st - 1;
            if (cur[0] + cur[1] < nrmax)
            {
                if (query(st) - query(st - 1) == 0)
                    update(st);
            }
            st++;
            p = st;
            if (cur[0] + cur[1] == nrmax)
            {
                ret_sc = cur[1];
                break;
            }
        }
    }
}

///a[i] = tipul lui i, nu prea imi pasa cat e V dar ce stiu e ca sunt sub sqrt(N) a[i] < V
///o sa incerc sa le gasesc pe fiecare in parte si dau query in ele
///pai mai intai gasesc primul de tip V, apoi voi tot incerca sa gasesc primul de tip < V de dupa si apoi brut pana la urmatorul de tip V
///asta cu binara, sigur da 90 ca e sqrtlog dar poate mai mult

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:44:9: warning: unused variable 'seen' [-Wunused-variable]
   44 |     int seen = 0;
      |         ^~~~
prize.cpp:92:17: warning: 'ret_sc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |                 if (cur[1] == ret_sc)
      |                 ^~

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