Submission #1280869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280869		aeg	Toxic Gene (NOI23_toxic)	C++20	81.10 / 100	8 ms	576 KiB

toxic

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

bool test(vector<int> &phs, vector<int> &ans, vector<int> &rs, int &ind) {
  int l = 0, r = phs.size() - 1;
  int anss = INT_MAX;
  while (l <= r) {
    int m = (l + r) >> 1;
    vector<int> quer;
    for (int i = 0; i <= m; i++)
      quer.push_back(phs[i] + 1);
    for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
      for (int j = 0; j < (1 << (i - ind)); j++) {
        quer.push_back(rs[i] + 1);
      }
    }
    int val = query_sample(quer);
    if (val == quer.size())
      l = m + 1;
    else {
      anss = min(anss, m);
      r = m - 1;
      for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
        if (val & (1 << (i - ind)))
          ans[rs[i]] = 2;
        else
          ans[rs[i]] = 1;
      }
      ind += 8;
    }
  }

  ans[phs[anss]] = 3;
  vector<int> newphs;
  for (int i = 0; i < anss; i++)
    newphs.push_back(phs[i]);
  for (int i = anss + 1; i < phs.size(); i++)
    newphs.push_back(phs[i]);
  phs = newphs;
  vector<int> quer = phs;
  for (auto &x : quer)
    x++;
  for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
    for (int j = 0; j < (1 << (i - ind)); j++) {
      quer.push_back(rs[i] + 1);
    }
  }
  int val = query_sample(quer);
  if (val == quer.size()) {
    for (auto &x : phs)
      ans[x] = 1;
    return false;
  }
  for (int i = ind; i < min(ind + 8, (int)rs.size()); i++) {
    if (val & (1 << (i - ind)))
      ans[rs[i]] = 2;
    else
      ans[rs[i]] = 1;
  }
  ind += 8;

  return true;
}

void test2(vector<int> &block, int tox, vector<int> &ans) {
  vector<int> quer(1, tox + 1);
  for (int i = 0; i < block.size(); i++) {
    for (int j = 0; j < (1 << i); j++)
      quer.push_back(block[i] + 1);
  }

  int val = query_sample(quer);
  for (int i = 0; i < block.size(); i++) {
    if (val & (1 << i)) {
      ans[block[i]] = 2;
    } else
      ans[block[i]] = 1;
  }
  block.clear();
}

void determine_type(int n) {
  vector<int> phs2;
  vector<int> ans(n,
                  0); // 0: unknown, 1: reg, 2: strong, 3:tox, -1: R/S, -2: R/T

  vector<int> rs;
  for (int i = 0; i < n; i += 8) {
    vector<int> quer;
    for (int j = i; j < min(n, i + 8); j++)
      for (int k = 0; k < (1 << (j - i)); k++)
        quer.push_back(j + 1);
    int val = query_sample(quer);
    if (val == quer.size())
      for (int j = i; j < min(n, i + 8); j++) {
        ans[j] = -1;
        rs.push_back(j);
      }
    else {
      phs2.push_back(i);
      for (int j = i; j < min(n, i + 8); j++) {
        if (val & (1 << (j - i)))
          ans[j] = 2;
        else
          ans[j] = -2;
      }
    }
  }

  int ind = 0;

  for (int i = 0; i < phs2.size(); i++) {
    vector<int> phs;
    for (int j = phs2[i]; j < min(n, phs2[i] + 8); j++)
      if (ans[j] == -2)
        phs.push_back(j);

    bool b = test(phs, ans, rs, ind);
    while (b)
      b = test(phs, ans, rs, ind);
  }

  int tox = 0;
  for (int i = 0; i < n; i++)
    if (ans[i] == 3)
      tox = i;

  vector<int> block;
  for (int i = 0; i < n; i++) {
    if (ans[i] <= 0)
      block.push_back(i);
    if (block.size() == 8)
      test2(block, tox, ans);
  }
  if (!block.empty())
    test2(block, tox, ans);

  for (int i = 0; i < n; i++)
    answer_type(i + 1, ans[i] == 1 ? 'R' : ans[i] == 2 ? 'S' : 'T');
}

• Subtask 1: 81.1 / 100