Submission #1019825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019825		andrei_iorgulescu	The Big Prize (IOI17_prize)	C++14	100 / 100	38 ms	5720 KiB

prize

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

using namespace std;

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

vector<int> askk(int pos)
{
    //pos = N + 1 - 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)
{
    N = n;
    int sn = 500;
    //int sn = 1;
    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];
        if (nrmax > 50)
        {
            sn = i;
            break;
        }
    }
    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;
        int cr = (n - st) / ret_sc + 10;
        dr = min(dr,st + cr);
        if (dr != dr0)
        {
            vector<int> lol = askk(dr);
            if (lol[0] + lol[1] == nrmax and lol[1] == ret_sc)
            {
                p = dr + 1;
                continue;
            }
            else if (lol[0] + lol[1] == 0)
                return dr - 1;
            else if (lol[0] + lol[1] < nrmax)
                pozi.insert(dr);
        }
        while (st < dr)
        {
            int mij = (st + dr) / 2;
            vector<int> cur = askk(mij);
            if (cur[0] + cur[1] < nrmax)
            {
                if (cur[0] + cur[1] == 0)
                    return mij - 1;
                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:32:9: warning: unused variable 'seen' [-Wunused-variable]
   32 |     int seen = 0;
      |         ^~~~
prize.cpp:47:9: warning: unused variable 'cate' [-Wunused-variable]
   47 |     int cate = nrmax;
      |         ^~~~
prize.cpp:59:27: warning: 'ret_sc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |         int cr = (n - st) / ret_sc + 10;
      |                  ~~~~~~~~~^~~~~~~~

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