Submission #1191107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191107		avighna	Toxic Gene (NOI23_toxic)	C++20	86.50 / 100	12 ms	328 KiB

toxic

#include "toxic.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <numeric>
#include <random>
#include <ranges>

int BinarySearchMin(int s, int e, const std::function<bool(int)> &f) {
  while (s < e) {
    int m = s + (e - s) / 2;
    if (f(m)) {
      e = m;
    } else {
      s = m + 1;
    }
  }
  return s;
}

void determine_type(int n) {
  std::vector<char> ans(n + 1);

  std::vector<int> p(n);
  std::iota(p.begin(), p.end(), 0);
  std::random_device rd;
  std::mt19937 gen(rd());
  std::shuffle(p.begin(), p.end(), gen);

  // with randomized index locs, new funcs
  auto query = [&](std::vector<int> sample) {
    for (auto &i : sample) {
      i = p[i - 1] + 1;
    }
    return query_sample(sample);
  };
  auto answer = [&](int i, char x) { answer_type(p[i - 1] + 1, x); };

  auto create_vec = [](int s, int e) {
    std::vector<int> ans;
    for (int i = s; i <= e; ++i) {
      ans.push_back(i);
    }
    return ans;
  };

  auto create_sample = [&](std::vector<int>::iterator begin,
                           std::vector<int>::iterator end) {
    std::vector<int> sample;
    for (int bt = 0; bt < 8 and begin != end; ++bt, ++begin) {
      for (int j = 0; j < (1 << bt); ++j) {
        sample.push_back(*begin);
      }
    }
    return sample;
  };

  std::vector<int> check; // normal, strong
  std::vector<int> naturals(n + 1);
  std::iota(naturals.begin(), naturals.end(), 0);
  int toxic_loc = 0;
  std::vector<int> future_queries(n + 1);
  std::vector<std::vector<int>> future_idxs(n + 1);
  std::vector<bool> modified(n + 1); // potentially removed toxic
  for (int i = 1; i <= n; i += 8) {
    auto sample = create_sample(naturals.begin() + i,
                                naturals.begin() + std::min(n + 1, i + 8));
    int mask = query(sample);
    if (mask == sample.size()) {
      for (int j = i; j <= std::min(n, i + 7); ++j) {
        check.push_back(j);
      }
    } else {
      std::vector<int> idxs;
      for (int j = i, bt = 0; j <= std::min(n, i + 7); ++j, ++bt) {
        if (mask & (1 << bt)) {
          ans[j] = 'S';
        } else {
          idxs.push_back(j);
        }
      }
      future_idxs[i] = idxs;
    }
    future_queries[i] = mask;
  }
  // move front elements to back
  auto pow_of_2 = [](int x) { return x > 0 && (x & (x - 1)) == 0; };

  auto to_pow_of_2 = [](int x) {
    if (x <= 0)
      return 1; // handle non-positive values safely
    if ((x & (x - 1)) == 0)
      return x; // already a power of 2
    int power = 1;
    while (power < x)
      power <<= 1;
    return power;
  };
  for (int i = n; i >= 1; --i) {
    if (future_idxs[i].empty() or pow_of_2(future_idxs[i].size())) {
      continue;
    }
    for (int j = 1; j < i and !pow_of_2(future_idxs[i].size()); ++j) {
      if (future_idxs[j].empty() or pow_of_2(future_idxs[j].size())) {
        continue;
      }
      while (future_idxs[i].size() < to_pow_of_2(future_idxs[i].size()) and
             !future_idxs[j].empty()) {
        future_idxs[i].push_back(future_idxs[j].back());
        future_idxs[j].pop_back();
        modified[j] = true;
      }
      std::sort(future_idxs[i].begin(), future_idxs[i].end());
    }
  }
  for (int i = 1; i <= n; i += 8) {
    auto sample = create_sample(naturals.begin() + i,
                                naturals.begin() + std::min(n + 1, i + 8));
    int mask = future_queries[i];
    if (mask != sample.size()) {
      std::vector<int> idxs = future_idxs[i];
      if (idxs.empty()) {
        continue;
      }
      do {
        if (modified[i] and query(idxs) == idxs.size()) {
          break;
        } else {
          modified[i] = false;
        }
        int pt = BinarySearchMin(0, idxs.size() - 1, [&](int j) {
          std::vector<int> sample; // only toxic and normal
          for (int k = 0; k <= j; ++k) {
            sample.push_back(idxs[k]);
          }
          // add some things we can basically do a free check with
          int k = 0; // number of things we added
          std::vector<int> things_rem;
          for (; k < 8 and !check.empty(); ++k) {
            for (int bt = 0; bt < (1 << k); ++bt) {
              sample.push_back(check.back());
            }
            things_rem.push_back(check.back());
            check.pop_back();
          }
          int mask = query(sample);
          if (mask == sample.size()) {
            for (auto &i : things_rem) {
              check.push_back(i);
            }
            return false;
          }
          for (int bt = 0; bt < k; ++bt) {
            if (mask & (1 << bt)) {
              ans[things_rem[bt]] = 'S';
            } else {
              ans[things_rem[bt]] = 'R';
            }
          }
          return true;
        });
        ans[idxs[pt]] = 'T';
        toxic_loc = idxs[pt];
        idxs.erase(idxs.begin() + pt);
        std::sort(idxs.begin(), idxs.end());
      } while (query(idxs) != idxs.size());
      for (int i = 0; i < idxs.size(); ++i) {
        ans[idxs[i]] = 'R';
      }
    }
  }

  for (int i = 0; i < check.size(); i += 8) {
    auto sample = create_sample(
        check.begin() + i, check.begin() + std::min(int(check.size()), i + 8));
    sample.push_back(toxic_loc); // normal and strong + one toxic
    auto mask = query(sample);
    for (int bt = 0; bt < 8 and i + bt < check.size(); ++bt) {
      if (mask & (1 << bt)) {
        ans[check[i + bt]] = 'S';
      } else {
        ans[check[i + bt]] = 'R';
      }
    }
  }

  for (int i = 1; i <= n; ++i) {
    answer(i, ans[i]);
  }
}

• Subtask 1: 86.5 / 100