Submission #766824

#	Time	Username	Problem	Language	Result	Execution time	Memory
766824		danikoynov	The Big Prize (IOI17_prize)	C++14	96.20 / 100	52 ms	1908 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
map < int, vector < int > > mp;
map < int, int > used;
int cnt = 0;
vector < int > local_ask(int idx)
{
    if (used[idx])
        return mp[idx];
    cnt ++;
    //if (cnt == 1e4)
    //  while(true);
    used[idx] = 1;
    mp[idx] = ask(idx);
    return mp[idx];
}

const int maxn = 2e5 + 10;
vector < int > st;
int best;
bool done = false;
void solve_range(int l, int r)
{
    if (done)
        return;
    ///cout << l << " " << r << " " << cnt << endl;
    int m = (l + r) / 2;
    vector < int > lf = local_ask(l);
    vector < int > rf = local_ask(r);
    if (lf[1] == rf[1])
        return;
    while(m > l)
    {
        vector < int > mf = local_ask(m);
        if (mf[0] + mf[1] != best)
        {
            if (mf[0] + mf[1] == 0)
                done = true;
            st.push_back(m);
            m --;
        }
        else
        {
            break;
        }
    }
    if (m == l)
    {
        m = (l + r) / 2 + 1;
        while(m < r)
        {
            vector < int > mf = local_ask(m);
            if (mf[0] + mf[1] != best)
            {
                            if (mf[0] + mf[1] == 0)
                done = true;
                st.push_back(m), m ++;
            }
            else
                break;
        }
    }
    if (m == r)
        return;

    vector < int > mf = local_ask(m);
    if (lf[0] != mf[0])
        solve_range(l, m);
    if (rf[0] != mf[0])
        solve_range(m, r);
}
int find_best(int n)
{
    vector < int > idc;
    for (int i = 0; i < n; i ++)
        idc.push_back(i);
    int nec = min(n, (int)sqrt(n) + 50);
    int mx = -1;
    for (int i = 0; i < nec; i ++)
    {
        vector < int > cur = local_ask(i);
        if (cur[0] + cur[1] > best)
        {
            best = cur[0] + cur[1];
            mx = i;
        }
    }
    int pt = n - 1;
    while(true)
    {
        vector < int > cur = local_ask(pt);
        if (cur[0] + cur[1] == best)
            break;
        pt --;
    }


    for (int i = 0; i < mx; i ++)
        st.push_back(i);
    for (int i = pt + 1; i < n; i ++)
        st.push_back(i);
    solve_range(mx, pt);

    //cout << st.size() << " " << cnt << endl;
    for (int i = 0; i < st.size(); i ++)
    {
        vector < int > cur = local_ask(st[i]);
        if (cur[0] + cur[1] == 0)
            return st[i];
    }
    return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < st.size(); i ++)
      |                     ~~^~~~~~~~~~~

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