Submission #1202551

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

routers

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

vector<int> find_routers(int l, int n, int q){
    vector<int> ans(n, 0);

    if (n == 2){
        int lo = 0, hi = l + 1;
        while (hi - lo > 1){
            int mid = lo + (hi - lo) / 2;
            if (use_detector(mid) == 0)
                lo = mid;
            else
                hi = mid;
        }
        ans[1] = 2 * lo;
        return ans;
    }

    for (int i = 1; i < n; i ++){
        int last = ans[i - 1], cur = 64;
        while (last + cur <= l and use_detector(last + cur) == i - 1)
            cur += 64;

        int lo = last + cur - 64, hi = min(l + 1, last + cur);
        while (hi - lo > 1){
            int mid = (lo + hi) / 2;
            if (use_detector(mid) == i - 1)
                lo = mid;
            else
                hi = mid;
        }
        ans[i] = 2 * lo - last;
    }
	return ans;
}

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