Submission #784688

#	Time	Username	Problem	Language	Result	Execution time	Memory
784688		Boas	Finding Routers (IOI20_routers)	C++17	39 / 100	1 ms	340 KiB

routers

#include "routers.h"
using namespace std;
// l is length
// n is number of routers
// q is max uses of detector
vector<int> find_routers(int l, int n, int q)
{
  vector<int> ans(n); // distance of each router i to the origin
  if (n == 2)
  {
    // find position of switch (first point where i = 1) using binary search
    int min = 2;
    int max = (l / 2) + 1;
    while (max - min > 0)
    {
      int k = (max + min) / 2;
      int i = use_detector(k);
      if (i == 0)
      {
        min = k + 1;
      }
      else
      {
        max = k;
      }
    }
    ans[1] = min + max - 2;
  }
  else
  {
    for (int i = 1; i < n; i++)
    {
      int locMin = ans[i - 1] + 2;
      int locMax = l - (2 * (n - 1 - i));
      int sMin = locMin;
      int sMax = (locMax / 2) + 1;
      while (sMax - sMin > 0)
      {
        int k = (sMax + sMin) / 2;
        int i = use_detector(k);
        if (i == 0)
        {
          sMin = k + 1;
        }
        else
        {
          sMax = k;
        }
      }
      ans[i] = sMin + sMax - 2;
    }
  }
  return ans;
}

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