Submission #1019738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019738		andrei_iorgulescu	The Big Prize (IOI17_prize)	C++17	90 / 100	55 ms	5972 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 find_best(int n)
{
    int sn = 2 * sqrt(n) + 1;
    sn = min(sn,n);
    int nrmax = 0,ret_sc;
    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];
    }
    if (n - nrmax <= 500)
        assert(false);
    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);
        while (st < dr)
        {
            int mij = (st + dr) / 2;
            vector<int> cur = askk(mij);
            if (cur[0] + cur[1] < nrmax)
                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;
            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:57:17: warning: 'ret_sc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |                 if (cur[1] == ret_sc)
      |                 ^~

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