Submission #863959

#	Time	Username	Problem	Language	Result	Execution time	Memory
863959		Ariadna	Finding Routers (IOI20_routers)	C++14	77.93 / 100	3 ms	1112 KiB

routers

#include <bits/stdc++.h>
 
using namespace std;
 
int use_detector(int x);

unordered_map < int, int > ans;

int query(int x) {
    if (ans.find(x) != ans.end()) return ans[x];
    return ans[x] = use_detector(x);
}

int detector(int l, int r, int router) {
    int low = r, hi = l;
    while (low < hi) {
        int m = (low + hi) / 2;
        if (query(m) >= router) hi = m;
        else low = m + 1;
    }
    return low;
}

vector < int > find_routers(int l, int n, int q) {
    vector < int > p(n);
    p[0] = 0;
    for (int i = 1; i < n; ++i) {
        p[i] = 2 * (detector(l, p[i - 1], i) - 1) - p[i - 1];
    }
    return p;
}

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