Submission #830615

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

toxic

#include "toxic.h"
#include <string>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int S = 8;	/* 2^S <= 300 */

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

unsigned int X;

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

void determine_type(int n) {
	vi pp(n);
	for (int i = 0; i < n; i++)
		pp[i] = i;
	X = 12345;
	for (int i = 0; i < n; i++) {
		int j = rand_() % (i + 1), tmp;
		tmp = pp[i], pp[i] = pp[j], pp[j] = tmp;
	}
	string cc(n, '?');
	int m = (n + S - 1) / S;
	vi has(m, 0), hh(m, 0); int m_ = 0;
	for (int h = 0; h < m; h++) {
		int l = h * S, r = min((h + 1) * S, n);
		vi ii;
		for (int i = l; i < r; i++)
			for (int t = 0; t < 1 << i - l; t++)
				ii.push_back(pp[i] + 1);
		int b = query_sample(ii);
		if (b == (1 << r - l) - 1)
			hh[m_++] = h;
		else {
			has[h] = 1;
			for (int i = l; i < r; i++)
				if ((b & 1 << i - l) != 0)
					cc[i] = 'S';
		}
	}
	for (int h = 0; h < m; h++) {
		if (!has[h])
			continue;
		int l = h * S, r = min((h + 1) * S, n);
		int lower = l, upper = r;
		while (1) {
			while (upper - lower > 1) {
				int i_ = (lower + upper) / 2;
				vi ii;
				for (int i = lower; i < i_; i++)
					ii.push_back(pp[i] + 1);
				if (m_ > 0) {
					int h_ = hh[m_ - 1], l_ = h_ * S, r_ = min((h_ + 1) * S, n);
					for (int i = l_; i < r_; i++)
						for (int t = 0; t < 1 << i - l_; t++)
							ii.push_back(pp[i] + 1);
				}
				int b = query_sample(ii);
				if (b == (int) ii.size())
					lower = i_;
				else {
					upper = i_;
					if (m_ > 0) {
						int h_ = hh[m_ - 1], l_ = h_ * S, r_ = min((h_ + 1) * S, n);
						for (int i = lower; i < i_; i++)
							if (cc[i] == 'S')
								b--;
						for (int i = l_; i < r_; i++)
							cc[i] = (b & 1 << i - l_) != 0 ? 'S' : 'R';
						m_--;
					}
				}
			}
			cc[lower++] = 'T';
			upper = r;
			vi ii;
			for (int i = lower; i < upper; i++)
				ii.push_back(pp[i] + 1);
			if (m_ > 0) {
				int h_ = hh[m_ - 1], l_ = h_ * S, r_ = min((h_ + 1) * S, n);
				for (int i = l_; i < r_; i++)
					for (int t = 0; t < 1 << i - l_; t++)
						ii.push_back(pp[i] + 1);
			}
			int b = ii.size() == 0 ? 0 : query_sample(ii);
			if (b == (int) ii.size())
				break;
			if (m_ > 0) {
				int h_ = hh[m_ - 1], l_ = h_ * S, r_ = min((h_ + 1) * S, n);
				for (int i = lower; i < upper; i++)
					if (cc[i] == 'S')
						b--;
				for (int i = l_; i < r_; i++)
					cc[i] = (b & 1 << i - l_) != 0 ? 'S' : 'R';
				m_--;
			}
		}
		for (int i = l; i < r; i++)
			if (cc[i] == '?')
				cc[i] = 'R';
	}
	int t = 0;
	while (cc[t] != 'T')
		t++;
	while (m_--) {
		int h = hh[m_], l = h * S, r = min((h + 1) * S, n);
		vi ii;
		ii.push_back(pp[t] + 1);
		for (int i = l; i < r; i++)
			for (int t = 0; t < 1 << i - l; t++)
				ii.push_back(pp[i] + 1);
		int b = query_sample(ii);
		for (int i = l; i < r; i++)
			cc[i] = (b & 1 << i - l) != 0 ? 'S' : 'R';
	}
	for (int i = 0; i < n; i++)
		answer_type(pp[i] + 1, cc[i]);
}

Compilation message (stderr)

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:35:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |    for (int t = 0; t < 1 << i - l; t++)
      |                             ~~^~~
toxic.cpp:38:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   38 |   if (b == (1 << r - l) - 1)
      |                  ~~^~~
toxic.cpp:43:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   43 |     if ((b & 1 << i - l) != 0)
      |                   ~~^~~
toxic.cpp:61:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |       for (int t = 0; t < 1 << i - l_; t++)
      |                                ~~^~~~
toxic.cpp:75:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   75 |        cc[i] = (b & 1 << i - l_) != 0 ? 'S' : 'R';
      |                          ~~^~~~
toxic.cpp:88:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   88 |      for (int t = 0; t < 1 << i - l_; t++)
      |                               ~~^~~~
toxic.cpp:100:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |      cc[i] = (b & 1 << i - l_) != 0 ? 'S' : 'R';
      |                        ~~^~~~
toxic.cpp:116:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  116 |    for (int t = 0; t < 1 << i - l; t++)
      |                             ~~^~~
toxic.cpp:120:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  120 |    cc[i] = (b & 1 << i - l) != 0 ? 'S' : 'R';
      |                      ~~^~~

• Subtask 1: 93.25 / 100