Submission #434870

#	Time	Username	Problem	Language	Result	Execution time	Memory
434870		kevinxiehk	Finding Routers (IOI20_routers)	C++17	100 / 100	9 ms	332 KiB

routers

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

int rb[1005];
int ans[1005];
void search(int a) {
    int l = ans[a - 1] + 1, r = rb[a];
    cerr << l << ' ' << r << '\n';
    while(l < r) {
        int m = (l + r + 1) / 2;
        int x = use_detector(m);
        for(int i = a; i <= x; i++) rb[i] = min(rb[i], m);
        if(x == a - 1) l = m;
        else r = m - 1;
    }
    ans[a] = (l - ans[a - 1]) * 2 + ans[a - 1];
    return;
}
vector<int> find_routers(int l, int n, int q) {
    for(int i = 0; i < n; i++) rb[i] = l;
    ans[0] = 0;
    for(int i = 1; i < n; i++) search(i);
    vector<int> rt;
    for(int i = 0; i < n; i++) rt.emplace_back(ans[i]);
    return rt;
}

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