Submission #810831

#	Time	Username	Problem	Language	Result	Execution time	Memory
810831		wortelworm	Finding Routers (IOI20_routers)	C++17	80.86 / 100	2 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

    // index, 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;
        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 {
                // if (result > i) {
                //     // I know additional information
                //     fill(upper_cache.begin())
                // }

                // the number is <= middle
                upper = middle;
            }
        }

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

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