Submission #830778

#	Time	Username	Problem	Language	Result	Execution time	Memory
830778		rainboy	Toxic Gene (NOI23_toxic)	C++17	100 / 100	10 ms	468 KiB

toxic

/* https://github.com/noisg/noi_2023/blob/master/final/model%20solutions/model_q5_toxic.cpp */
#include "toxic.h"
#include <cstring>
#include <vector>

using namespace std;

typedef vector<bool> vb;
typedef vector<int> vi;

const int N = 300, K = 8, B = (N + K - 1) / K;	/* K = floor(log2(N)) */

int min(int a, int b) { return a < b ? a : b; }

unsigned int X;

int rand_() {
	return (X *= 3) >> 1;
}

int ii[N], ii_[N], jj[N], n_, m; char cc[N + 1], has[B];

void shuffle(int *ii, int n) {
	X = 12345;
	for (int i = 0; i < n; i++) {
		int j = rand_() % (i + 1), tmp;
		tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
	}
}

void search(int *ii, int n) {
	int lower = 0, upper = n;
	while (upper - lower > 1) {
		int mid = (lower + upper) / 2;
		vi qq;
		for (int h = lower; h < mid; h++)
			qq.push_back(ii[h] + 1);
		int k = min(m, K);
		for (int h = m - k; h < m; h++)
			for (int t = 0; t < 1 << h - m + k; t++)
				qq.push_back(jj[h] + 1);
		int b = query_sample(qq);
		if (b == qq.size()) {
			for (int h = lower; h < mid; h++)
				cc[ii[h]] = 'R';
			lower = mid;
		} else {
			for (int h = mid; h < upper; h++)
				ii_[n_++] = ii[h];
			for (int h = m - k; h < m; h++)
				cc[jj[h]] = (b & 1 << h - m + k) != 0 ? 'S' : 'R';
			m -= k;
			upper = mid;
		}
	}
	cc[ii[lower]] = 'T';
}

void determine_type(int n) {
	int n1 = n;
	memset(cc, '?', n * sizeof *cc);
	for (int i = 0; i < n; i++)
		ii[i] = i;
	shuffle(ii, n);
	for (int g = 0; g * K < n; g++) {
		int l = g * K, r = min((g + 1) * K, n);
		vi qq;
		for (int h = l; h < r; h++)
			for (int t = 0; t < 1 << h - l; t++)
				qq.push_back(ii[h] + 1);
		int b = query_sample(qq);
		if (b == (1 << r - l) - 1) {
			has[g] = 0;
			for (int h = l; h < r; h++)
				jj[m++] = ii[h];
		} else {
			has[g] = 1;
			for (int h = l; h < r; h++)
				if ((b & 1 << h - l) != 0)
					cc[ii[h]] = 'S';
		}
	}
	n_ = 0;
	for (int g = 0; g * K < n; g++)
		if (has[g]) {
			int l = g * K, r = min((g + 1) * K, n), k = 0;
			for (int h = l; h < r; h++)
				if (cc[ii[h]] != 'S')
					ii[l + k++] = ii[h];
			search(ii + l, k);
		}
	memcpy(ii, ii_, (n = n_) * sizeof *ii_);
	while (n > 0) {
		shuffle(ii, n);
		n_ = 0;
		for (int g = 0; g * K < n; g++) {
			int l = g * K, r = min((g + 1) * K, n);
			vi qq;
			for (int h = l; h < r; h++)
				qq.push_back(ii[h] + 1);
			int k = min(m, K);
			for (int h = m - k; h < m; h++)
				for (int t = 0; t < 1 << h - m + k; t++)
					qq.push_back(jj[h] + 1);
			int b = query_sample(qq);
			if (b == qq.size())
				for (int h = l; h < r; h++)
					cc[ii[h]] = 'R';
			else {
				for (int h = m - k; h < m; h++)
					cc[jj[h]] = (b & 1 << h - m + k) != 0 ? 'S' : 'R';
				m -= k;
				search(ii + l, r - l);
			}
		}
		memcpy(ii, ii_, (n = n_) * sizeof *ii_);
	}
	int t = 0;
	while (cc[t] != 'T')
		t++;
	while (m > 0) {
		int k = min(m, K);
		vi qq;
		qq.push_back(t + 1);
		for (int h = m - k; h < m; h++)
			for (int t = 0; t < 1 << h - m + k; t++)
				qq.push_back(jj[h] + 1);
		int b = query_sample(qq);
		for (int h = m - k; h < m; h++)
			cc[jj[h]] = (b & 1 << h - m + k) != 0 ? 'S' : 'R';
		m -= k;
	}
	for (int i = 0; i < n1; i++)
		answer_type(i + 1, cc[i]);
}

Compilation message (stderr)

toxic.cpp: In function 'void search(int*, int)':
toxic.cpp:40:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   40 |    for (int t = 0; t < 1 << h - m + k; t++)
      |                             ~~~~~~^~~
toxic.cpp:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   if (b == qq.size()) {
      |       ~~^~~~~~~~~~~~
toxic.cpp:51:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   51 |     cc[jj[h]] = (b & 1 << h - m + k) != 0 ? 'S' : 'R';
      |                           ~~~~~~^~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:69:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |    for (int t = 0; t < 1 << h - l; t++)
      |                             ~~^~~
toxic.cpp:72:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   72 |   if (b == (1 << r - l) - 1) {
      |                  ~~^~~
toxic.cpp:79:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   79 |     if ((b & 1 << h - l) != 0)
      |                   ~~^~~
toxic.cpp:103:36: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  103 |     for (int t = 0; t < 1 << h - m + k; t++)
      |                              ~~~~~~^~~
toxic.cpp:106:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    if (b == qq.size())
      |        ~~^~~~~~~~~~~~
toxic.cpp:111:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  111 |      cc[jj[h]] = (b & 1 << h - m + k) != 0 ? 'S' : 'R';
      |                            ~~~~~~^~~
toxic.cpp:126:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  126 |    for (int t = 0; t < 1 << h - m + k; t++)
      |                             ~~~~~~^~~
toxic.cpp:130:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  130 |    cc[jj[h]] = (b & 1 << h - m + k) != 0 ? 'S' : 'R';
      |                          ~~~~~~^~~

• Subtask 1: 100 / 100