oj.uz

Submission #829813

# Submission time Handle Problem Language Result Execution time Memory
829813 2023-08-18T15:12:01 Z rainboy Toxic Gene (NOI23_toxic) C++17
58.15 / 100
 9 ms 392 KB 
#include "toxic.h"
#include <string>
#include <vector>

using namespace std;

typedef vector<int> vi;

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

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

void determine_type(int n) {
	string cc(n, '?');
	int m = (n + S - 1) / S;
	vi done(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(i + 1);
		int b = query_sample(ii);
		if (b == (1 << r - l) - 1)
			continue;
		for (int i = l; i < r; i++)
			if ((b & 1 << i - l) != 0)
				cc[i] = 'S';
		int lower = l, upper = r;
		while (1) {
			while (upper - lower > 1) {
				int i_ = (lower + upper) / 2;
				ii.clear();
				for (int i = lower; i < i_; i++)
					ii.push_back(i + 1);
				if (query_sample(ii) == i_ - lower)
					lower = i_;
				else
					upper = i_;
			}
			cc[lower++] = 'T';
			upper = r;
			ii.clear();
			for (int i = lower; i < upper; i++)
				ii.push_back(i + 1);
			if (ii.size() == 0 || query_sample(ii) == upper - lower)
				break;
		}
		for (int i = l; i < r; i++)
			if (cc[i] == '?')
				cc[i] = 'R';
	}
	int t = 0;
	while (cc[t] != 'T')
		t++;
	for (int h = 0; h < m; h++) {
		int l = h * S, r = min((h + 1) * S, n);
		if (cc[l] != '?')
			continue;
		vi ii;
		ii.push_back(t + 1);
		for (int i = l; i < r; i++)
			for (int t = 0; t < 1 << i - l; t++)
				ii.push_back(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(i + 1, cc[i]);
}

Compilation message

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:21:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   21 |    for (int t = 0; t < 1 << i - l; t++)
      |                             ~~^~~
toxic.cpp:24:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |   if (b == (1 << r - l) - 1)
      |                  ~~^~~
toxic.cpp:27:20: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |    if ((b & 1 << i - l) != 0)
      |                  ~~^~~
toxic.cpp:63:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |    for (int t = 0; t < 1 << i - l; t++)
      |                             ~~^~~
toxic.cpp:67:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |    cc[i] = (b & 1 << i - l) != 0 ? 'S' : 'R';
      |                      ~~^~~

Subtask #1
58.15 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Partially correct 6 ms 332 KB Partially correct
3 Partially correct 6 ms 324 KB Partially correct
4 Partially correct 6 ms 392 KB Partially correct
5 Partially correct 6 ms 340 KB Partially correct
6 Partially correct 5 ms 340 KB Partially correct
7 Partially correct 5 ms 340 KB Partially correct
8 Partially correct 5 ms 340 KB Partially correct
9 Partially correct 9 ms 392 KB Partially correct
10 Partially correct 6 ms 332 KB Partially correct
11 Partially correct 5 ms 340 KB Partially correct
12 Partially correct 7 ms 340 KB Partially correct
13 Partially correct 6 ms 340 KB Partially correct
14 Partially correct 6 ms 340 KB Partially correct
15 Partially correct 5 ms 332 KB Partially correct
16 Partially correct 5 ms 332 KB Partially correct
17 Partially correct 5 ms 388 KB Partially correct
18 Partially correct 5 ms 340 KB Partially correct
19 Partially correct 6 ms 340 KB Partially correct
20 Partially correct 5 ms 340 KB Partially correct
21 Partially correct 5 ms 340 KB Partially correct
22 Partially correct 5 ms 340 KB Partially correct
23 Partially correct 5 ms 384 KB Partially correct
24 Correct 6 ms 388 KB Output is correct
25 Correct 6 ms 368 KB Output is correct
26 Correct 6 ms 340 KB Output is correct
27 Correct 6 ms 368 KB Output is correct
28 Correct 6 ms 340 KB Output is correct
29 Correct 6 ms 388 KB Output is correct
30 Correct 7 ms 368 KB Output is correct
31 Correct 6 ms 340 KB Output is correct
32 Partially correct 6 ms 388 KB Partially correct
33 Correct 6 ms 340 KB Output is correct
34 Partially correct 5 ms 340 KB Partially correct
35 Partially correct 5 ms 340 KB Partially correct
36 Partially correct 1 ms 212 KB Partially correct