Submission #1200711

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

routers

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

vector<int> dis;

void rec(int s, int e, int l, int r) {
  if(s>e) return;
  if(e-s == r-l) {
    for(int i=l; i<=r; i++) dis.push_back(i);
    return;
  }
  if(r-l==1) {
    if(use_detector(r)==s) dis.push_back(r);
    else dis.push_back(l);
    return;
  }
  int mid = l+r>>1;
  int wh = use_detector(mid);
  rec(s, wh-1, l, mid-1);
  rec(wh, e, mid, r);
}

vector<int> find_routers(int L, int n, int q) {
  rec(0, n-2, 0, L-1);
  vector<int> ans = {0};
  for(int i : dis)
    ans.push_back(2*i-ans.back());
  return ans;
}

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