oj.uz

Submission #933298

# Submission time Handle Problem Language Result Execution time Memory
933298 2024-02-25T11:54:47 Z zhaohaikun Toxic Gene (NOI23_toxic) C++17
8.27308 / 100
 7 ms 1368 KB 
#include "toxic.h"
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) {return mrand() % (r - l + 1) + l;}
int t[310], ans[310][310], pre[310];
bool vis[310];
vector <int> g;
void solve(int l, int r) {
	if (l == r) {
		vis[l] = true;
		g.push_back(l);
		return;
	}
	int mid = (l + r) >> 1;
	vector <int> p, q;
	F(i, l, mid) p.push_back(t[i]);
	F(i, mid + 1, r) q.push_back(t[i]);
	if ((ans[l][mid] = query_sample(p)) != p.size()) solve(l, mid);
	if ((ans[mid + 1][r] = query_sample(q)) != q.size()) solve(mid + 1, r);
}
vector <int> f;
void dot(int l, int r, int s) {
	// for (int i: w) cout << i << " "; cout << endl;
	// int f = query_sample(w);
	int S = pre[r] - pre[l - 1];
	// debug << l << " " << r << " " << S << " " << s << endl;
	if (s == 0) {
		F(i, l, r)
			if (!vis[i]) answer_type(t[i], 'R');//, debug << i << endl;
		return;
	}
	if (s == S) {
		F(i, l, r)
			if (!vis[i]) answer_type(t[i], 'S');//, debug << i << endl;
		return;
	}
	int mid = (l + r) >> 1;
	if ((~ans[l][mid]) && ans[l][mid] != mid - l + 1) {
		dot(l, mid, ans[l][mid]), dot(mid + 1, r, s - ans[l][mid]);
	} else if ((~ans[mid + 1][r]) && ans[mid + 1][r] != r - mid) {
		dot(l, mid, s - ans[mid + 1][r]), dot(mid + 1, r, ans[mid + 1][r]);
	} else {
		vector <int> w;
		F(i, l, mid)
			if (!vis[i]) w.push_back(t[i]);
		w.push_back(t[g[0]]);
		int f = query_sample(w);
		// debug << l << " " << mid 
		dot(l, mid, f), dot(mid + 1, r, s - f);
	}
}
void determine_type(int n) {
	ms(vis, false);
	ms(ans, -1);
	f.clear();
	g.clear();
	F(i, 1, n) t[i] = i;
	shuffle(t + 1, t + n + 1, mrand);
	vector <int> w;
	F(i, 1, n) w.push_back(i);
	// w.push_back(t[g[0]]);
	ans[1][n] = query_sample(w);
	solve(1, n);
	for (int i: g) answer_type(t[i], 'T');//, debug << i << endl;
	F(i, 1, n) pre[i] = pre[i - 1] + (!vis[i]);
	// for (int i: g) debug << i << endl;
	// g.insert(g.begin(), 0);
	// g.push_back(n + 1);
	// F(i, 1, n)
	// 	if (!count(all(g), i)) f.push_back(t[i]);
	// vector <int> w;
	// F(i, 1, n)
	// 	if (!vis[i]) w.push_back(t[i]);
	// w.push_back(t[g[0]]);
	dot(1, n, ans[1][n]);
	// int B = 10;
	// for (int l = 1, r; l <= f.size(); l = r + 1) {
	// 	r = min((int) f.size(), l + B - 1);
	// 	vector <int> w;
	// 	F(i, l, r) w.push_back(f[i - 1]);
	// 	w.push_back(t[g[0]]);
	// 	// dot(1, f.size(), query_sample(w));
	// 	dot(l, r, query_sample(w));
	// }
	// F(i, 0, SZ(g) - 1)
	// 	if (g[i] + 1 != g[i + 1]) dot(g[i] + 1, g[i + 1] - 1);
}

Compilation message

toxic.cpp: In function 'void solve(int, int)':
toxic.cpp:36:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  if ((ans[l][mid] = query_sample(p)) != p.size()) solve(l, mid);
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
toxic.cpp:37:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  if ((ans[mid + 1][r] = query_sample(q)) != q.size()) solve(mid + 1, r);
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
8.27307692 / 100.0

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