Submission #1230101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230101		altern23	Finding Routers (IOI20_routers)	C++20	77.95 / 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 = ans[i - 1] + 1, rg = l - (n - i - 1), 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: 17.9456 / 40