Submission #1230158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230158		sethod	Finding Routers (IOI20_routers)	C++20	77.95 / 100	2 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);
  ans[0] = 0;
  vector<int> road(l + 1, -1);
  for(int i = 1; i < n; i++){
    int lft = ans[i - 1] + 1;
    int r = l - (n - i - 1);
    int pos = -1;
    while(lft <= r){
      int m = (lft + r) / 2;
      if(road[m] == -1) road[m] = use_detector(m);
      if(road[m] >= i){ 
        r = m - 1;
        pos = m;
      }
      else lft = m + 1;
    }
    int tmp = pos - ans[i - 1];
		ans[i] = pos + (tmp - 1) - 1;
  }
	return ans;
}

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