Submission #1201170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201170		The_Samurai	Finding Routers (IOI20_routers)	C++20	100 / 100	44 ms	592 KiB

routers

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

map<int, int> mp;
int ask(int x) {
    if (mp.count(x)) return mp[x];
    return mp[x] = use_detector(x);
}

std::vector<int> find_routers(int l, int n, int q) {
    vector<tuple<int, int, int>> v;
    vector<bool> used(n);
    int last = 0;
    for (int i = 0; i < n - 1; i++) {
        set<int> st;
        for (auto it: mp) {
            if (it.first >= last) st.insert(it.second);
        }
        int exp;
        if (st.size() == n - i) {
            for (auto it: mp) {
                if (it.first < last) continue;
                exp = it.second;
                break;
            }
        } else exp = i == 0 ? 0 : ask(last);
        int lx = last + 1, rx = l - (n - i - 1), best = last;
        for (auto it: mp) {
            if (it.second == exp) lx = it.first + 1;
            if (it.first < last or it.second == exp) continue;
            rx = it.first - 1;
            break;
        }
        best = lx - 1;
        while (lx <= rx) {
            int mid = (lx + rx) >> 1;
            if (ask(mid) == exp) {
                best = mid;
                lx = mid + 1;
            } else {
                rx = mid - 1;
            }
        }
        used[exp] = true;
        v.emplace_back(exp, last, best);
        last = best + 1;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) v.emplace_back(i, last, l);
    }
    vector<int> ans(n);
    for (int i = 1; i < n; i++) {
        auto [a, b] = make_pair(get<0>(v[i - 1]), get<0>(v[i]));
        int start = ans[a], mid = get<2>(v[i - 1]);
        // cout << a << ' ' << b << ' ' << start << ' ' << mid << endl;
        if (a > b) mid++;
        ans[b] = mid + (mid - start);
        // cout << '\t' << ans[b] << endl;
    }
    return ans;
}

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