oj.uz

답안 #950995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950995 2024-03-21T03:48:18 Z GrandTiger1729 Toxic Gene (NOI23_toxic) C++17
95.95 / 100
 70 ms 1520 KB 
#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;

const int K = 8, T = 30;
vector<int> encode(vector<int> qry)
{
	int n = qry.size();
	vector<int> ret;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < (1 << i); j++)
		{
			ret.push_back(qry[i]);
		}
	}
	return ret;
}
void determine_type(int n)
{
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 1);
	srand(mt19937(time(0))());
	mt19937 randint(time(0));
	random_shuffle(ord.begin(), ord.end());
	string ans(n + 1, 'R');
	int cnt = 0;
	int tt = -1;
	vector<int> stk;
	int i = 0;
	while (cnt < T && i < n)
	{
		int j = min(n, i + K);
		int xx = -1;
		{
			vector<int> qry;
			for (int k = i; k < j; k++)
			{
				qry.push_back(ord[k]);
			}
			int x = min(stk.size(), K - qry.size());
			for (int k = 0; k < x; k++)
			{
				qry.push_back(stk.end()[-1 - k]);
			}
			xx = query_sample(encode(qry));
			if (xx == (1 << qry.size()) - 1)
			{
				stk.insert(stk.end(), qry.begin(), qry.end());
				i = j;
				continue;
			}
			else
			{
				for (int k = j - i; k < qry.size(); k++)
				{
					ans[qry[k]] = (xx >> k & 1) ? 'S' : 'R';
				}
				for (int k = 0; k < x; k++)
				{
					stk.pop_back();
				}
			}
		}
		auto make_query = [&](int mid)
		{
			vector<int> qry;
			for (int k = i; k < mid; k++)
			{
				qry.push_back(ord[k]);
			}
			int x = min(stk.size(), K - qry.size());
			for (int k = 0; k < x; k++)
			{
				qry.push_back(stk.end()[-1 - k]);
			}
			return qry;
		};
		int l = i, r = j;
		while (l < r - 1)
		{
			int mid = (l + r) / 2;
			vector<int> qry = make_query(mid);
			int res = query_sample(encode(qry));
			if (res == (1 << qry.size()) - 1)
			{
				l = mid;
			}
			else
			{
				int x = qry.size() - (mid - i);
				for (int k = mid - i; k < qry.size(); k++)
				{
					ans[qry[k]] = (res >> k & 1) ? 'S' : 'R';
				}
				for (int k = 0; k < x; k++)
				{
					stk.pop_back();
				}
				r = mid;
			}
		}
		vector<int> qry = make_query(l);
		for (int k = 0; k < l - i; k++)
		{
			ans[qry[k]] = (xx >> k & 1) ? 'S' : 'R';
		}
		cerr << "ans " << ans << endl;
		ans[ord[l]] = 'T';
		cerr << "OK " << l << ' ' << ord[l] << endl;
		i = l + 1;
		tt = ord[l];
		cnt++;
	}
	while (i < n)
	{
		stk.push_back(ord[i++]);
	}
	cerr << ans << endl;
	for (int j = 0; j < stk.size(); j++)
	{
		cerr << stk[j] << endl;
	}
	cerr << "tt " << tt << endl;
	while (stk.size())
	{
		int x = min((int)stk.size(), K);
		vector<int> qry;
		for (int k = 0; k < x; k++)
		{
			qry.push_back(stk.back());
			stk.pop_back();
		}
		auto tmp = encode(qry);
		tmp.push_back(tt);
		int res = query_sample(tmp);
		for (int k = 0; k < (int)qry.size(); k++)
		{
			ans[qry[k]] = (res >> k & 1) ? 'S' : 'R';
		}
	}
	cerr << ans << endl;
	for (int j = 1; j <= n; j++)
	{
		answer_type(j, ans[j]);
	}
}

Compilation message

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int k = j - i; k < qry.size(); k++)
      |                         ~~^~~~~~~~~~~~
toxic.cpp:92:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int k = mid - i; k < qry.size(); k++)
      |                           ~~^~~~~~~~~~~~
toxic.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int j = 0; j < stk.size(); j++)
      |                  ~~^~~~~~~~~~~~

Subtask #1
95.95 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 68 ms 948 KB Output is correct
3 Correct 59 ms 1048 KB Output is correct
4 Correct 55 ms 1076 KB Output is correct
5 Correct 42 ms 1360 KB Output is correct
6 Correct 42 ms 1364 KB Output is correct
7 Correct 43 ms 1452 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 42 ms 1372 KB Output is correct
10 Correct 45 ms 1424 KB Output is correct
11 Correct 46 ms 1456 KB Output is correct
12 Correct 57 ms 1104 KB Output is correct
13 Correct 56 ms 1104 KB Output is correct
14 Correct 57 ms 852 KB Output is correct
15 Partially correct 46 ms 1360 KB Partially correct
16 Correct 47 ms 1360 KB Output is correct
17 Partially correct 45 ms 1464 KB Partially correct
18 Partially correct 46 ms 1360 KB Partially correct
19 Partially correct 59 ms 1360 KB Partially correct
20 Partially correct 47 ms 1360 KB Partially correct
21 Correct 56 ms 1492 KB Output is correct
22 Correct 59 ms 1108 KB Output is correct
23 Correct 57 ms 860 KB Output is correct
24 Correct 70 ms 880 KB Output is correct
25 Correct 55 ms 1088 KB Output is correct
26 Correct 55 ms 1108 KB Output is correct
27 Correct 59 ms 1052 KB Output is correct
28 Correct 55 ms 1104 KB Output is correct
29 Partially correct 48 ms 1296 KB Partially correct
30 Correct 47 ms 1416 KB Output is correct
31 Partially correct 51 ms 1440 KB Partially correct
32 Correct 46 ms 1360 KB Output is correct
33 Correct 44 ms 1440 KB Output is correct
34 Partially correct 45 ms 1520 KB Partially correct
35 Partially correct 45 ms 1388 KB Partially correct
36 Correct 6 ms 344 KB Output is correct