Submission #485575

#	Time	Username	Problem	Language	Result	Execution time	Memory
485575		dxz05	Finding Routers (IOI20_routers)	C++14	77.94 / 100	2 ms	716 KiB

routers

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

int mem[100005];
int ask(int x){
    if (mem[x] == -1) mem[x] = use_detector(x);
    return mem[x];
}

vector<int> find_routers(int len, int n, int q){
    fill(mem, mem + len + 1, -1);

    vector<int> p(n);

    for (int i = 1; i < n; i++){
        int l = p[i - 1] + 1, r = len;
        while (l <= r) {
            int m = (l + r) >> 1;
            if (ask(m) == i - 1){
                l = m + 1;
            } else r = m - 1;
        }

        l--;
        p[i] = 2 * l - p[i - 1];

    }

    return p;
}

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