Submission #290140

#	Time	Username	Problem	Language	Result	Execution time	Memory
290140		SamAnd	The Big Prize (IOI17_prize)	C++17	100 / 100	68 ms	5336 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 200005;

vector<int> vv[N];
vector<int> qry(int x)
{
    if (!vv[x].empty())
        return vv[x];
    return vv[x] = ask(x);
}

int s;

int ans;
bool rec(int l, int r, int ql, int qr)
{
    if (l > r)
        return false;
    int m = (l + r) / 2;
    while (m <= r)
    {
        if (qry(m)[0] + qry(m)[1] == s)
        {
            if (qry(m)[0] - ql > 0)
                if (rec(l, m - 1, ql, qry(m)[1]))
                    return true;
            if (qry(m)[1] - qr > 0)
                if (rec(m + 1, r, qry(m)[0], qr))
                    return true;
            return false;
        }
        else
        {
            if (qry(m)[0] + qry(m)[1] == 0)
            {
                ans = m;
                return true;
            }
            ++m;
        }
    }
    --m;
    while (m >= l)
    {
        if (qry(m)[0] + qry(m)[1] == s)
        {
            if (qry(m)[0] - ql > 0)
                if (rec(l, m - 1, ql, qry(m)[1]))
                    return true;
            if (qry(m)[1] - qr > 0)
                if (rec(m + 1, r, qry(m)[0], qr))
                    return true;
            return false;
        }
        else
        {
            if (qry(m)[0] + qry(m)[1] == 0)
            {
                ans = m;
                return true;
            }
            --m;
        }
    }
    ++m;
    return false;
}

int find_best(int n)
{
    for (int x = 0; x < min(n, 700); ++x)
    {
        s = max(s, qry(x)[0] + qry(x)[1]);
        if (s > 100)
            break;
    }
    assert(rec(0, n - 1, 0, 0));
    return ans;
}

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