Submission #1201581

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

routers

#include "routers.h"
#include <bits/stdc++.h>

using namespace std;

//int use_detector(int x){
//    cout << x << endl;
//    int ans; cin >> ans;
//    return ans;
//}

void dnc(int l, int r, int u, int v, vector<int> &cutting_points){
    if (l > r) return;
    if (u == v) {
        cutting_points[v] = max(cutting_points[v], r);
        return;
    }
    int mid = (l + r) / 2;
    int belonging = use_detector(mid);
    cutting_points[belonging] = max(cutting_points[belonging], mid);
    dnc(l, mid - 1, u, belonging, cutting_points);
    dnc(mid+1, r, belonging, v, cutting_points);
}

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

    return p;
}

//int main(void){
//    ios::sync_with_stdio(0); cin.tie(0);
//
//    vector<int> ans = find_routers(5, 2, 10);
//    for(int i: ans) cout << i << " ";
//    cout << "\n";
//
//    return 0;
//}

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