Submission #941250

#	Time	Username	Problem	Language	Result	Execution time	Memory
941250		marvinthang	Toxic Gene (NOI23_toxic)	C++17	100 / 100	12 ms	600 KiB

toxic

/*************************************
*    author: marvinthang             *
*    created: 08.03.2024 10:14:19    *
*************************************/
// https://www.acmicpc.net/problem/28499

#include "toxic.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

#ifdef LOCAL
int N, num_que; 
string S;
vector <bool> used;
int query_sample(vector <int> species) {
	if ((int) species.size() > 300) {
		cout << "ngu sz = " << species.size() << '\n';
		exit(0);
	}
	++num_que;
	bool has_toxic = false;
	for (int x: species) {
		if (x < 1 || x > N) {
			cout << "ngu query " << x << '\n';
			exit(0);
		}
		has_toxic |= S[x - 1] == 'T';
	}
	if (has_toxic) {
		int res = 0;
		for (int x: species) res += S[x - 1] == 'S';
		return res;
	}
	return species.size();
}
void answer_type(int x, char c) {
	if (x < 1 || x > N) {
		cout << "ngu answer " << x << '\n';
		exit(0);
	}
	if (used[x - 1]) {
		cout << "ngu answer twice\n";
		exit(0);
	}
	used[x - 1] = true;
	if (S[x - 1] != c) {
		cout << "ngu res[" << x << "] = " << S[x - 1] << ", yours = " << c << '\n';
		exit(0);
	}
}
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); } 
template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); } 

void determine_type(int n) {
	int toxic = -1;
	vector <int> cur(n);
	iota(ALL(cur), 1);
	shuffle(ALL(cur), rng);
	string res(n + 1, '?');
	int cnt_toxic = 0;
	vector <vector <int>> tox, not_tox;
	for (int i = 0; i < n; i += 8) {
		vector <int> List;
		FOR(j, i, min(n, i + 8)) List.push_back(cur[j]);
		vector <int> cur;
		REP(i, List.size()) REP(j, MASK(i)) cur.push_back(List[i]);
		int mask = query_sample(cur);
		if (mask == MASK(List.size()) - 1) {
			not_tox.push_back(List);
		} else {
			tox.push_back({});
			REP(i, List.size()) {
				if (BIT(mask, i)) res[List[i]] = 'S';
				else tox.back().push_back(List[i]);
			}
		}
	}
	auto check_tox = [&] (vector <int> cur) {
		if (!not_tox.empty()) {
			REP(i, not_tox.back().size()) REP(j, MASK(i)) cur.push_back(not_tox.back()[i]);
		}
		int mask = query_sample(cur);
		if (mask < (int) cur.size()) {
			if (!not_tox.empty()) {
				REP(i, not_tox.back().size()) res[not_tox.back()[i]] = "RS"[BIT(mask, i)];
				not_tox.pop_back();
			}
			return true;
		}
		return false;
	};
	vector <int> new_tox;
	auto solve = [&] (vector <int> &List, bool ck) {
		if (ck) {
			if (!check_tox(List)) {
				for (int x: List) res[x] = 'R';
				return;
			}
		}
		int l = 0, r = (int) List.size() - 2;
		while (l <= r) {
			int m = l + r >> 1;
			vector <int> cur(List.begin(), List.begin() + m + 1);
			if (check_tox(cur))	r = m - 1;
			else l = m + 1;
		}
		REP(i, l) res[List[i]] = 'R';
		res[List[l]] = 'T';
		toxic = List[l];
		new_tox.insert(new_tox.end(), l + 1 + ALL(List));
		++cnt_toxic;
	};
	for (auto List: tox) solve(List, false);
	while (!new_tox.empty() && cnt_toxic < 30) {
		vector <int> List;
		while ((int) List.size() < 8 && !new_tox.empty()) {
			List.push_back(new_tox.back());
			new_tox.pop_back();
		}
		solve(List, true);
	}
	for (int x: new_tox) res[x] = 'R';
	for (auto List: not_tox) {
		vector <int> cur{toxic};
		REP(i, List.size()) REP(j, MASK(i)) cur.push_back(List[i]);
		int mask = query_sample(cur);
		REP(i, List.size()) res[List[i]] = "RS"[BIT(mask, i)];
	}
	FORE(i, 1, n) answer_type(i, res[i]);
}

#ifdef LOCAL 
int main(void) {
	file("TOXIC");
	int t; cin >> t;
	int max_que = 0;
	while (t--) {
		cin >> N >> S;
		used.assign(N, false);
		num_que = 0;
		determine_type(N);
		if (accumulate(ALL(used), 0) < N) {
			cout << "ngu not enough answer\n";
			return 0;
		}
		max_que = max(max_que, num_que);
	}
	cout << "max_que = " << max_que << '\n';
	return 0;
}
#endif

Compilation message (stderr)

toxic.cpp: In lambda function:
toxic.cpp:141:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |    int m = l + r >> 1;
      |            ~~^~~

• Subtask 1: 100 / 100