Submission #989070

#	Time	Username	Problem	Language	Result	Execution time	Memory
989070		AdamGS	Finding Routers (IOI20_routers)	C++17	100 / 100	1 ms	452 KiB

routers

#include "routers.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
vector<int>T;
void solve(int l, int r, int a, int b) {
  T[a]=min(T[a], l);
  if(a==b) return;
  if(l+1>=r) {
    T[a]=min(T[a], l);
    return;
  }
  int mid=(l+r)/2;
  int x=use_detector(mid);
  solve(l, mid, a, x);
  solve(mid, r, x, b);
}
vector<int>find_routers(int l, int n, int q) {
  rep(i, n) T.pb(l);
  solve(0, l, 0, n-1);
  vector<int>ans;
  ans.pb(0);
  rep(i, n-1) {
    int x=T[i+1]-ans.back()-1;
    ans.pb(ans.back()+2*x);
  }
  return ans;
}

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