Submission #1190765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190765		avighna	Toxic Gene (NOI23_toxic)	C++20	26.07 / 100	6 ms	328 KiB

toxic

#include "toxic.h"
#include <algorithm>
#include <numeric>
#include <random>
#include <ranges>
#include <set>

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

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

  int toxic_loc =
      *std::ranges::partition_point(std::views::iota(1, n + 1), [&](int i) {
        std::vector<int> sample = create_vec(1, i);
        return sample.size() == query_sample(sample);
      });

  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> naturals(n + 1);
  std::iota(naturals.begin(), naturals.end(), 0);
  std::vector<int> check; // normal, toxic
  for (int i = 1; i <= n; i += 8) {
    auto sample = create_sample(naturals.begin() + i,
                                naturals.begin() + std::min(n + 1, i + 8));
    if (query_sample(sample) == (1 << 8) - 1) {
      sample.push_back(toxic_loc);
      int mask = query_sample(sample);
      for (int bt = 0; bt < 8 and i + bt <= n; ++bt) {
        if (mask & (1 << bt)) {
          ans[i + bt] = 'S';
        } else {
          ans[i + bt] = 'R';
        }
      }
    } else {
      sample.push_back(toxic_loc);
      int mask = query_sample(sample);
      for (int bt = 0; bt < 8 and i + bt <= n; ++bt) {
        if (mask & (1 << bt)) {
          ans[i + bt] = 'S';
        } else {
          check.push_back(i + bt);
        }
      }
    }
  }

  std::random_device rd;
  std::mt19937 rng(rd());
  std::shuffle(check.begin(), check.end(), rng);
  for (int i = 0; i < check.size(); i += 2) {
    std::string map = "TR";
    if (i == check.size() - 1) {
      ans[check[i]] = map[query_sample({check[i]})];
      continue;
    }
    if (query_sample({check[i], check[i + 1]}) == 2) {
      ans[check[i]] = ans[check[i + 1]] = 'R';
    } else {
      ans[check[i]] = map[query_sample({check[i]})];
      ans[check[i + 1]] = map[query_sample({check[i + 1]})];
    }
  }

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

• Subtask 1: 26.0706 / 100