Submission #385701

#	Time	Username	Problem	Language	Result	Execution time	Memory
385701		taulant	Finding Routers (IOI20_routers)	C++14	100 / 100	7 ms	1132 KiB

routers

#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> pii;

int use_detector(int);

vector<int> find_routers(int l, int n, int q){
 set<pii> s;
 s.insert({0,0});
 s.insert({n,l});
 map<int, int> m;
 vector<int> ret(n); // ret[0] = 0
 for(int i = 1; i < n; ++i){
  int lo = ret[i-1], hi = l;
  auto ir = s.lower_bound({i, 0}), il = ir;
  --il;
  lo = max(lo, il -> second), hi = min(hi, ir -> second);
  while(lo < hi){
   int mid = (lo + hi + 1) / 2;
   int x = m.count(mid)? m[mid] : use_detector(mid);
   s.insert({x, mid});
   m[mid] = x;
   if(x < i) lo = mid;
   else hi = mid - 1;
  }
  ret[i] = lo + lo - ret[i-1];
 }
 return ret;
}

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