Submission #1200446

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

routers

#include "routers.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> find_routers(int L, int n, int q) 
{
  int K = 64;
  // while (K < L / (n - 1)) K <<= 1;
  vector<int> x = {0};
  int last = 0, l = 1;
  while (x.size() < n)
  {
    int y = use_detector(min(L, last + K));
    while (x.size() != y + 1)
    {
      int r = min(L, last + K);
      while (l < r)
      {
        int mid = (l + r) >> 1;
        if (use_detector(mid) <= (int)x.size() - 1) l = mid + 1;
        else r = mid;
      }
      x.push_back(l);
      l++;
    }
    last += K;
    l = last + 1;
  }
  vector<int> res = {0};
  for (int i = 1; i < n; i++)
  {
    int d = x[i] - 1 - res[i - 1];
    res.push_back(res[i - 1] + d * 2);
  }
  return res;
}

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