Submission #810842

#	Time	Username	Problem	Language	Result	Execution time	Memory
810842		wortelworm	Finding Routers (IOI20_routers)	C++17	99.26 / 100	1 ms	724 KiB

routers

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

vector<int> query_cache;
int customQuery(int x) {
    if (query_cache[x] >= 0) {
        return query_cache[x];
    }

    int result = use_detector(x);
    query_cache[x] = result;
    return result;
}


std::vector<int> find_routers(int length, int n, int _q) {
    vector<int> answers(n);
    // go to closest (lower_eq) even number
    int global_upper = length & (~1);

    query_cache.assign(length + 1, -1);

    // for numbers up to x, y is the upper limit

    //  until index, stricter upper
    set<pair<int, int>> upper_cache;

    for (int i = 1; i < n; i++)
    {
        // find router i
        int minimum = answers[i - 1];

        // even, exclusive
        int lower = minimum;

        // even, inclusive
        int upper = global_upper;
        auto it = upper_cache.lower_bound({i, 0});
        if (it != upper_cache.end()) {
            upper = (*it).second;
        }

        while (lower + 2 < upper) {
            int middle = (lower + upper) / 2;
            if (middle % 2 == 1) {
                middle --;
            }
            int test = minimum + (middle - minimum) / 2 + 1;
            int result = customQuery(test);
            if (result < i) {
                // the number is > middle
                lower = middle;
            } else {
                // the number is <= middle
                upper = middle;
                if (result > i) {
                    // I know additional information
                    auto [it, added] = upper_cache.insert({result, upper});

                    if (added) {
                        // remove some from upper_cache as well?
                        while (it != upper_cache.begin()) {
                            it--;
                            if ((*it).second <= upper) {
                                break;
                            }
                            it = upper_cache.erase(it);
                        }
                    }
                }
            }
        }

        answers[i] = lower + 2;
    }
    
    return answers;
}

• Subtask 1: 16 / 16
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 39.260799999999996 / 40