oj.uz

Submission #829927

# Submission time Handle Problem Language Result Execution time Memory
829927 2023-08-18T15:55:23 Z rainboy Toxic Gene (NOI23_toxic) C++17
64.9 / 100
 9 ms 372 KB 
#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;
	int z = -1;
	while (n > 0) {
		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;
		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) {
				for (int i = l; i < r; i++)
					cc[i] = '!';
				continue;
			}
			for (int i = l; i < r; i++)
				if ((b & 1 << i - l) != 0)
					cc[i] = 'S';
			int lower = l, upper = r;
			while (upper - lower > 1) {
				int i_ = (lower + upper) / 2;
				ii.clear();
				for (int i = lower; i < i_; i++)
					ii.push_back(pp[i] + 1);
				if (query_sample(ii) == i_ - lower) {
					for (int i = lower; i < i_; i++)
						if (cc[i] == '?')
							cc[i] = 'R';
					lower = i_;
				} else
					upper = i_;
			}
			cc[lower] = 'T';
		}
		int t = 0;
		while (t < n && cc[t] != 'T')
			t++;
		if (t < n)
			z = pp[t];
		for (int h = 0; h < m; h++) {
			int l = h * S, r = min((h + 1) * S, n);
			if (cc[l] == '!') {
				vi ii;
				ii.push_back(z + 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';
			}
		}
		int n_ = 0;
		for (int i = 0; i < n; i++)
			if (cc[i] == '?')
				pp[n_++] = pp[i];
			else
				answer_type(pp[i] + 1, cc[i]);
		n = n_;
	}
}

Compilation message

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:36:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |     for (int t = 0; t < 1 << i - l; t++)
      |                              ~~^~~
toxic.cpp:39:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   39 |    if (b == (1 << r - l) - 1) {
      |                   ~~^~~
toxic.cpp:45:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |     if ((b & 1 << i - l) != 0)
      |                   ~~^~~
toxic.cpp:74:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   74 |      for (int t = 0; t < 1 << i - l; t++)
      |                               ~~^~~
toxic.cpp:78:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   78 |      cc[i] = (b & 1 << i - l) != 0 ? 'S' : 'R';
      |                        ~~^~~

Subtask #1
64.9 / 100.0

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