Submission #1202509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202509		rafsanamin2020	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	584 KiB

routers

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

// subtask 1, 3

int g(std::vector<int> &memo, int p)
{
  // cout << memo[p] << " xx-";
  if (memo[p] == -1)
  {
    int k = use_detector(p);
    memo[p] = k;
    return k;
  }
  return memo[p];
}

void find_set(int n, int i, int l, int &idx, std::vector<int> &ans, std::vector<int> &memo)
{
  int L = 0, R = l, M = (L + R) / 2;
  while (L < R)
  {
    M = (L + R) / 2;
    int lbl = g(memo, M);
    // cout << L << " " << R << " " << M << " " << "\n";
    if (lbl < i)
    {
      L = M + 1;
    }
    else
    {
      R = M;
    }
  }
  idx = idx + 2 * (L - 1 - idx);
  ans[i] = idx;
}

std::vector<int> find_routers(int l, int n, int q)
{
  int idx = use_detector(0);
  std::vector<int> memo(l + 1, -1);
  std::vector<int> ans(n, l);
  ans[0] = idx;

  for (int i = 1; i < n; i++)
  {
    find_set(n, i, l, idx, ans, memo);
    // find_set(n, n - i, idx, ans);
  }
  // for (int x : ans)
  // {
  //   cout << x << " ";
  // }
  // for (int i = 0; i < n; i++)
  // {
  //   ans.push_back(0);
  // }
  // cout << (L - 1) << endl;

  return ans;
}

// subtask 2
// std::vector<int> find_routers(int l, int n, int q)
// {
//   std::vector<int> ans;
//   int prev = 0;
//   int idx = use_detector(0), h = 1;
//   ans.push_back(idx);
//   for (int i = 1; i <= l; i++)
//   {
//     int f = use_detector(i);

//     if (f != prev)
//     {
//       idx = (2 * i - 2 - idx);
//       ans.push_back(idx);
//       prev = f;
//     }
//   }
//   for (int x : ans)
//   {
//     cout << x << " ";
//   }
//   return ans;
// }

// std::vector<int> find_routers(int l, int n, int q)
// {
//   std::vector<int> ans;
//   int prev = 0;
//   int idx = use_detector(0), h = 1;
//   ans.push_back(idx);
//   for (int i = 1; i <= l; i++)
//   {
//     int f = use_detector(i);

//     if (f != prev)
//     {
//       idx = (2 * i - 2 - idx);
//       ans.push_back(idx);
//       prev = f;
//     }
//   }
//   for (int x : ans)
//   {
//     cout << x << " ";
//   }
//   return ans;
// }

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