Submission #941366

#	Time	Username	Problem	Language	Result	Execution time	Memory
941366		nguyentunglam	Toxic Gene (NOI23_toxic)	C++17	100 / 100	11 ms	552 KiB

toxic

#include<bits/stdc++.h>
#include "toxic.h"
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;

const int N = 300 + 10, T = 8;
int order[N], ans[N];
bool not_toxic[N];

char type[3] = {'R', 'S', 'T'};

mt19937 rng(324857235);

#ifdef ngu
int cnt_query;
char a[N], b[N];
int query_sample(vector<int> species) {
  cnt_query++;
  bool toxic = 0;
  for(int &j : species) toxic |= a[j] == 'T';
  int ret = 0;
  for(int &j : species) {
    if (a[j] == 'S') ret++;
    else if (a[j] == 'R' && !toxic) ret++;
  }
  return ret;
}

void answer_type(int x, char c) {
  b[x] = c;
}
#endif // ngu

vector<int> strong_regular, toxic_regular;

bool check (vector<int> candidate) {
  vector<int> share;
  while (!strong_regular.empty() && share.size() < T) {
    share.push_back(strong_regular.back());
    strong_regular.pop_back();
  }
  for(int j = 0; j < share.size(); j++) {
    int cnt = 1 << j;
    while (cnt--) candidate.push_back(share[j]);
  }
  int result = query_sample(candidate);
  if (result == candidate.size()) {
    for(int &j : share) strong_regular.push_back(j);
    for(int &j : candidate) not_toxic[j] = 1;
    return false;
  }
  for(int j = 0; j < share.size(); j++) {
    if (result >> j & 1) ans[share[j]] = 1;
  }
  return true;
}

int Search (vector<int> candidate) {
  if (candidate.size() == 1) return candidate.back();
  vector<int> left, right;
  int mid = (int) candidate.size() / 2;
  for(int i = 0; i < mid; i++) left.push_back(candidate[i]);
  for(int i = mid; i < candidate.size(); i++) right.push_back(candidate[i]);
  if (!left.empty() && check(left)) return Search(left);
  return Search(right);
}

void determine_type (int n) {
  for(int i = 1; i <= n; i++) order[i] = i, ans[i] = not_toxic[i] = 0;
  shuffle(order + 1, order + n + 1, rng);
  for(int i = 1; i <= n; i += T) {
//    cout << cnt_query << endl;
    vector<int> ask;
    int border = min(i + T - 1, n);
    for(int j = i; j <= border; j++) {
      int cnt = 1 << j - i;
      while (cnt--) ask.push_back(order[j]);
    }
    int result = query_sample(ask);
    int full = 1 << (border - i + 1); full--;
//    cout << result << " " << i << endl;
    if (result == full) {
      for(int j = i; j <= border; j++) strong_regular.push_back(order[j]);
    }
    else {
      vector<int> candidate;
      for(int j = i; j <= border; j++) {
        int delta = j - i;
        if (result >> delta & 1) ans[order[j]] = 1;
        else candidate.push_back(order[j]);
      }
      int x = Search(candidate);
      ans[x] = 2;
      for(int &j : candidate) if (j != x && not_toxic[j] == 0) toxic_regular.push_back(j);
    }
  }

//  for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;

  while (!toxic_regular.empty()) {
    vector<int> candidate;
    while (!toxic_regular.empty() && candidate.size() < 8) {
      candidate.push_back(toxic_regular.back());
      toxic_regular.pop_back();
    }
    if (check(candidate)) {
      int x = Search(candidate);
      ans[x] = 2;
      for(int &j : candidate) if (j != x && not_toxic[j] == 0) toxic_regular.push_back(j);
    }
  }

  int toxic = 0;
  for(int i = 1; i <= n; i++) if (ans[i] == 2) toxic = i;

//  cout << toxic << endl;

  while (!strong_regular.empty()) {
    vector<int> cur;
    while (!strong_regular.empty() && cur.size() < T) {
      cur.push_back(strong_regular.back());
      strong_regular.pop_back();
    }
    vector<int> ask = {toxic};
    for(int j = 0; j < cur.size(); j++) {
      int cnt = 1 << j;
      while (cnt--) ask.push_back(cur[j]);
    }
    int result = query_sample(ask);
    for(int j = 0; j < cur.size(); j++) {
      if (result >> j & 1) ans[cur[j]] = 1;
      else ans[cur[j]] = 0;
    }
  }

//  for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
  for(int i = 1; i <= n; i++) {
    answer_type(i, type[ans[i]]);
  }
}

#ifdef ngu
int main() {

  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);

  int t; cin >> t;

  while (t--) {
    cnt_query = 0;
    int n; cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i];

    determine_type(n);

    for(int i = 1; i <= n; i++) assert(a[i] == b[i]);

    for(int i = 1; i <= n; i++) cout << b[i] << " "; cout << endl;
//    assert(cnt_query <= 600);
    assert(cnt_query <= 150);
    cerr << cnt_query << endl;
  }
}
#endif // ngu

Compilation message (stderr)

toxic.cpp: In function 'bool check(std::vector<int>)':
toxic.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int j = 0; j < share.size(); j++) {
      |                  ~~^~~~~~~~~~~~~~
toxic.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   if (result == candidate.size()) {
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~
toxic.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j = 0; j < share.size(); j++) {
      |                  ~~^~~~~~~~~~~~~~
toxic.cpp: In function 'int Search(std::vector<int>)':
toxic.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i = mid; i < candidate.size(); i++) right.push_back(candidate[i]);
      |                    ~~^~~~~~~~~~~~~~~~~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:79:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   79 |       int cnt = 1 << j - i;
      |                      ~~^~~
toxic.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int j = 0; j < cur.size(); j++) {
      |                    ~~^~~~~~~~~~~~
toxic.cpp:133:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int j = 0; j < cur.size(); j++) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 100 / 100