Submission #1230242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230242		altern23	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	584 KiB

routers

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

vector<int> find_routers(int l, int n, int q) {
	vector<int> ans(n), dp(l + 1, -1);
	ans[0] = 0;
    for(int i = 1; i < n; i++){
		int lf = 0, rg = l, pos = -1;
		for(;lf <= rg;){
			int md = (lf + rg) / 2;
			int val = (dp[md] == -1 ? use_detector(md) : dp[md]);
			dp[md] = val;
			if(val >= i){
				pos = md;
				rg = md - 1;
			}
			else lf = md + 1;
		}
		int sz = pos - ans[i - 1];
		ans[i] = pos + (sz - 1) - 1;
	}
	return ans;
}

/*
0 0 0 1 1
*/

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