Submission #52384

#	Time	Username	Problem	Language	Result	Execution time	Memory
52384		WLZ	The Big Prize (IOI17_prize)	C++17	100 / 100	54 ms	956 KiB

prize

#include "prize.h"
#include <vector>
#include <stack>
#include <utility>
#include <map>

std::map<int, std::map<int, std::pair<int, int> > > mp;

int find_best(int n) {
    std::stack< std::pair<int, int> > st;
    st.emplace(0, n - 1);
    while (!st.empty()) {
        int lo = st.top().first;
        int hi = st.top().second;
        st.pop();
        int mid = (lo + hi) / 2;
        std::vector<int> q = ask(mid);
        int l = q[0], r = q[1];
        // the same type nodes are mp[l+r], key in mp[l+r] is the possible possition
        // sort mp[l+r]'s key using upper_bound to find the first position that is after mid
        // if for that position p1, r[p1] == r[mid], then we know we don't need push right interval
        // upper_bound -1 is the position that is before or equal to mid
        // if for that position p2, l[p2] == l[mid], then we know we don't need push left interval
        auto rIt = mp[l + r].upper_bound(mid);

        bool processLeft = true, processRight = true;
        if (!(rIt == mp[l + r].begin())) {
            // check if left interval can be ignored
            auto lIt = rIt; --lIt;
            if (lIt->second.first == l) {
                processLeft = false;
            }
        }
        if ((!(rIt == mp[l + r].end()) && rIt->second.second == r)||(r == 0)) {
            processRight = false;
        }

        
        mp[l + r][mid] = {l, r};
        if (l == 0 && r == 0) return mid;
        if (l == 0) st = std::stack< std::pair<int, int> >();
        if (lo != mid && processLeft) st.emplace(lo, mid - 1);
        if (hi != mid && processRight) st.emplace(mid + 1, hi);
    }
	return 0;
}

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