Submission #741385

#	Time	Username	Problem	Language	Result	Execution time	Memory
741385		josanneo22	Finding Routers (IOI20_routers)	C++17	100 / 100	1 ms	340 KiB

routers

#include "routers.h"
using namespace std;
 
#include <cstdio>
 
const int MAX_N = 1000;
int splits[MAX_N];
 
void find_splits(int l, int r, int first_split, int last_split) {
    if(first_split <= last_split && r - l > 1) {
        int mid = (l + r) / 2;
        int mid_split = use_detector(mid);
        
        find_splits(l, mid, first_split, mid_split - 1);
        find_splits(mid, r, mid_split, last_split);
    } else if(r - l == 1) {
        for(int i = first_split; i <= last_split; ++i)
            splits[i] = l;
    }
}
 
std::vector<int> find_routers(int l, int n, int q) {
    find_splits(0, l + 1, 0, n - 2);
    std::vector<int> pos;
    
    pos.push_back(0);
    for(int i = 0; i < n - 1; ++i)
        pos.push_back(2 * splits[i] - pos.back());
    
    return pos;
}

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