Submission #355369

#	Time	Username	Problem	Language	Result	Execution time	Memory
355369		dolphingarlic	Finding Routers (IOI20_routers)	C++14	100 / 100	3 ms	512 KiB

routers

#include "routers.h"

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

pair<int, int> rng[1000];

void search_ranges(int l, int r, int a, int b) {
    if (a > b) return;
    if (a == b) {
        rng[a] = {l, r};
        return;
    }
    int mid = (l + r + 1) / 2;
    int piv = use_detector(mid);
    search_ranges(l, mid - 1, a, piv);
    search_ranges(mid, r, piv + 1, b);
}

vector<int> find_routers(int len, int n, int q) {
    search_ranges(0, len, 1, n - 1);
    vector<int> ans = {0};
    for (int i = 1; i < n; i++) {
        int l, r;
        tie(l, r) = rng[i];
        while (l != r) {
            int mid = (l + r + 1) / 2;
            if (use_detector(mid) == i) r = mid - 1;
            else l = mid;
        }
        ans.push_back(2 * l - ans.back());
    }
    return ans;
}

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