Submission #766762

#	Time	Username	Problem	Language	Result	Execution time	Memory
766762		danikoynov	The Big Prize (IOI17_prize)	C++14	20 / 100	12 ms	4800 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;

int subsolve(vector < int > st)
{
    /**for (int i = 0; i < st.size(); i ++)
        cout << st[i] << " ";
    cout << endl;*/
    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 = ask(st[i]);
        if (cur[0] + cur[1] > best)
        {
            best = cur[0] + cur[1];
            mx = st[i];
        }
    }

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

    int t = mx, found = 0;
    vector < int > base = ask(mx);
    while(true)
    {
        int l = t + 1, r = st.size() - 1;
        while(l <= r)
        {
            int m = (l + r) / 2;
            vector < int > cur = 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 'int subsolve(std::vector<int>)':
prize.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if (l == st.size())
      |             ~~^~~~~~~~~~~~

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