Submission #1230418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230418		djsksbrbf	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 ln, int n, int q) {
	vector <int> v(n);v[0] = 0;
	
	int dp[ln + 1];memset(dp, -1, sizeof(dp));
	for(int i = 1 ; i < n ; i++){
		int l = 0, r = ln;
		
		int ans = -1;
		while(l <= r){
			int mid = (l + r) >> 1;
			
			if(dp[mid] == -1)dp[mid] = use_detector(mid);
			
			if(dp[mid] < i)l = mid + 1;
			else{
				ans  =mid;
				r = mid - 1;
			}
		}
		v[i] = (ans) + (ans - v[i - 1] - 1) - 1;
	}
	
	return v;
}

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