Submission #1201606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201606		steveonalex	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	328 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
using namespace std;
void dnc(int l, int r, int u, int v, vector<int> &cut){
    if (l > r) return;
    if (u == v) {
        cut[v] = max(cut[v], r);
        return;
    }
    int mid = (l + r) / 2;
    int split = use_detector(mid);
    cut[split] = max(cut[split], mid);
    dnc(l, mid - 1, u, split, cut);
    dnc(mid+1, r, split, v, cut);
}
vector<int> find_routers(int l, int n, int q){
    vector<int> p(n);
    vector<int> cut(n);
    dnc(0, l, 0, n-1, cut);
    for(int i = 1; i < n; ++i){
        int L = cut[i-1];
        p[i] = p[i-1] + 2 * (L - p[i-1]);
    }
    return p;
}

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