Submission #863915

#	Time	Username	Problem	Language	Result	Execution time	Memory
863915		Ariadna	Finding Routers (IOI20_routers)	C++14	60 / 100	2 ms	600 KiB

routers

#include <bits/stdc++.h>
 
using namespace std;
 
int use_detector(int x);
 
vector < int > two_routers(int l) {
    vector < int > p(2);
    p[0] = 0;
    int low = 0, hi = l;
    while (low < hi) {
        int m = (low + hi) / 2;
        if (use_detector(m)) hi = m;
        else low = m + 1;
    }
    p[1] = 2 * (low - 1);
    return p;
}

vector < int > find_routers(int l, int n, int q) {
    if (n == 2) return two_routers(l);
    vector < int > p(n);
    p[0] = 0;
    vector < int > aux(n, 0);
    for (int i = 1; i <= l; ++i) {
        aux[use_detector(i)]++;
    }
    for (int i = 1; i < n; ++i) {
        p[i] = p[i - 1] + 2 * aux[i - 1];
        aux[i] -= aux[i - 1];
    }
    return p;
}

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