Submission #941295

#	Time	Username	Problem	Language	Result	Execution time	Memory
941295		nguyentunglam	Toxic Gene (NOI23_toxic)	C++17	38.49 / 100	10 ms	668 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];

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

mt19937 rng(1);

#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

void Search (vector<int> candidate) {
  if (candidate.size() == 1) {
    ans[candidate.back()] = 2;
    return;
  }
  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() && query_sample(left) == 0) Search(left);
  if (!right.empty() && query_sample(right) == 0) Search(right);
}

void determine_type (int n) {
  for(int i = 1; i <= n; i++) order[i] = i, ans[i] = 0;
  shuffle(order + 1, order + n + 1, rng);
  vector<vector<int> > double_check;
  for(int i = 1; i <= n; i += T) {
    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 << " " << full << endl;
//    for(int &j : ask) cout << j << " "; cout << "#\n";
    if (result == full) {
      vector<int> tmp;
      for(int j = i; j <= border; j++) tmp.push_back(order[j]);
      double_check.push_back(tmp);
    }
    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]);
      }
      Search(candidate);
    }
  }

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

  int toxic = 0;
  for(int i = 1; i <= n; i++) if (ans[i] == 2) toxic = i;
  for(auto &arr : double_check) {
    int cur = 1;
    vector<int> ask = {toxic};
    for(int j = 0; j < arr.size(); j++) {
      int cnt = 1 << j;
      while (cnt--) ask.push_back(arr[j]);
    }
    int result = query_sample(ask);
    for(int j = 0; j < arr.size(); j++) {
      if (result >> j & 1) ans[arr[j]] = 1;
    }
  }

  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);

    cerr << cnt_query << endl;
  }
}
#endif // ngu

Compilation message (stderr)

toxic.cpp: In function 'void Search(std::vector<int>)':
toxic.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i = mid; i < candidate.size(); i++) right.push_back(candidate[i]);
      |                    ~~^~~~~~~~~~~~~~~~~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:57:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   57 |       int cnt = 1 << j - i;
      |                      ~~^~~
toxic.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int j = 0; j < arr.size(); j++) {
      |                    ~~^~~~~~~~~~~~
toxic.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int j = 0; j < arr.size(); j++) {
      |                    ~~^~~~~~~~~~~~
toxic.cpp:85:9: warning: unused variable 'cur' [-Wunused-variable]
   85 |     int cur = 1;
      |         ^~~

• Subtask 1: 38.49411765 / 100