Submission #766780

#	Time	Username	Problem	Language	Result	Execution time	Memory
766780		danikoynov	The Big Prize (IOI17_prize)	C++14	20 / 100	3062 ms	3384 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];
}
int subsolve(vector < int > st)
{
    /**for (int i = 0; i < st.size(); i ++)
        cout << st[i] << " ";
    cout << endl;*/
    if (st.size() < 5000)
    {
        ///cout << "size " << st.size() << endl;
        for (int i = 0; i < st.size(); i ++)
        {
            vector < int > cur = ask(st[i]);
            if (cur[0] + cur[1] == 0)
                return st[i];
        }
    }
    if (st.size() == 1)
        return st[0];

    int nec = min((int)(st.size()), (int)(sqrt(st.size()) + 2));
    int mx = -1, best = 0;
    for (int i = 0; i < nec; i ++)
    {
        vector < int > cur = local_ask(st[i]);
        if (cur[0] + cur[1] > best)
        {
            best = cur[0] + cur[1];
            mx = i;
        }
    }

    vector < int > level;
    for (int i = 0; i < mx; i ++)
        level.push_back(st[i]);

    int t = mx, found = 0;
    ///cout << "here " << mx << endl;
    vector < int > base = local_ask(mx);
    while(t < st.size())
    {
        int l = t + 1, r = st.size() - 1;
        ///cout << t << endl;
        while(l <= r)
        {
            int m = (l + r) / 2;
            vector < int > cur = local_ask(st[m]);
            if (cur[0] + cur[1] != best)
                r = m - 1;
            else
            {
                int bet = cur[0] - base[0] - found;
                if (bet != 0)
                    r = m - 1;
                else
                    l = m + 1;
            }
        }
        if (l == st.size())
            break;
        t = l;
        found ++;
        level.push_back(st[t]);
    }
    return subsolve(level);
}
int find_best(int n) {
    vector < int > idc;
    for (int i = 0; i < n; i ++)
        idc.push_back(i);
    int ans = subsolve(idc);
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'std::vector<int> local_ask(int)':
prize.cpp:9:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    9 |     if (used[idx])
      |     ^~
prize.cpp:11:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   11 |         cnt ++;
      |         ^~~
prize.cpp: In function 'int subsolve(std::vector<int>)':
prize.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < st.size(); i ++)
      |                         ~~^~~~~~~~~~~
prize.cpp:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while(t < st.size())
      |           ~~^~~~~~~~~~~
prize.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if (l == st.size())
      |             ~~^~~~~~~~~~~~

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