oj.uz

Submission #870011

# Submission time Handle Problem Language Result Execution time Memory
870011 2023-11-06T15:44:24 Z rainboy Mouse (info1cup19_mouse) C++17
100 / 100
 31 ms 444 KB 
#include "grader.h"

using namespace std;

typedef vector<int> vi;

const int N = 256;

vi pp, qq; int kk[N], n;
int ii[N], m; char good[N];

int solve(int hl, int hr, int kl, int kr) {
	if (kl == kr) {
		for (int h = hl; h < hr; h++)
			good[h] = 0;
		return 0;
	}
	if (hr - hl == 1) {
		good[hl] = 1;
		return 0;
	}
	int hm = (hl + hr) / 2;
	for (int i = 0; i < n; i++)
		qq[i] = pp[i];
	for (int h = 0; h < hm; h++)
		qq[ii[h]] = pp[ii[h + 1]];
	qq[ii[hm]] = pp[0];
	for (int h = hm + 1; h < m; h++)
		qq[ii[h]] = pp[ii[h]];
	qq[0] = pp[ii[0]];
	int km = query(qq);
	if (km == n)
		return 1;
	return solve(hl, hm, kl, km) || solve(hm, hr, km, kr);
}

void solve(int n_) {
	n = n_;
	pp.clear(), pp.resize(n);
	for (int i = 0; i < n; i++)
		pp[i] = i + 1;
	kk[0] = query(pp);
	if (kk[0] == n)
		return;
	bool good0 = true;
	for (int i = 1; i < n; i++) {
		pp[0] = i + 1, pp[i] = 1, kk[i] = query(pp), pp[0] = 1, pp[i] = i + 1;
		if (kk[i] == n)
			return;
		if (kk[0] <= kk[i])
			good0 = false;
	}
	m = 0;
	if (good0) {
		for (int i = 1; i < n; i++)
			if (kk[i] != kk[0] - 2)
				ii[m++] = i;
	} else {
		int u = -1, v = -1;
		for (int i = 1; i < n; i++)
			if (kk[i] == kk[0])
				ii[m++] = i;
			else if (kk[i] > kk[0]) {
				if (u == -1)
					u = i;
				else
					v = i;
			}
		if (v == -1)
			pp[0] = u + 1, pp[u] = 1;
		else {
			pp[0] = u + 1, pp[u] = v + 1, pp[v] = 1;
			int k = query(pp);
			if (k == n)
				return;
			if (k < kk[0] + 2) {
				int tmp;
				tmp = u, u = v, v = tmp;
				pp[0] = u + 1, pp[u] = v + 1, pp[v] = 1;
				k = query(pp);
				if (k == n)
					return;
			}
			if (k == kk[0] + 2)
				ii[m++] = u;
		}
	}
	qq.clear(), qq.resize(n);
	while (1) {
		for (int i = 0; i < n; i++)
			qq[i] = pp[i];
		for (int h = 0; h < m; h++)
			qq[ii[h]] = pp[ii[(h + 1) % m]];
		int k = query(qq);
		if (k == n || solve(0, m, n - m - 1, k - 1))
			return;
		for (int h = 0; h < m; h++)
			qq[ii[h]] = pp[ii[(h + 1) % m]];
		for (int h = 0; h < m; h++)
			pp[ii[h]] = qq[ii[h]];
		int m_ = 0;
		for (int h = 0; h < m; h++)
			if (!good[h])
				ii[m_++] = ii[h];
		m = m_;
	}
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 15
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 0 ms 344 KB Correct! Number of queries: 11
4 Correct 0 ms 344 KB Correct! Number of queries: 13
5 Correct 0 ms 344 KB Correct! Number of queries: 11
6 Correct 1 ms 344 KB Correct! Number of queries: 13

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 15
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 0 ms 344 KB Correct! Number of queries: 11
4 Correct 0 ms 344 KB Correct! Number of queries: 13
5 Correct 0 ms 344 KB Correct! Number of queries: 11
6 Correct 1 ms 344 KB Correct! Number of queries: 13
7 Correct 2 ms 344 KB Correct! Number of queries: 300
8 Correct 2 ms 344 KB Correct! Number of queries: 300
9 Correct 3 ms 344 KB Correct! Number of queries: 300
10 Correct 2 ms 344 KB Correct! Number of queries: 300
11 Correct 1 ms 344 KB Correct! Number of queries: 200
12 Correct 2 ms 344 KB Correct! Number of queries: 300
13 Correct 2 ms 344 KB Correct! Number of queries: 200
14 Correct 2 ms 344 KB Correct! Number of queries: 300
15 Correct 2 ms 344 KB Correct! Number of queries: 300
16 Correct 2 ms 344 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct! Number of queries: 15
2 Correct 0 ms 344 KB Correct! Number of queries: 6
3 Correct 0 ms 344 KB Correct! Number of queries: 11
4 Correct 0 ms 344 KB Correct! Number of queries: 13
5 Correct 0 ms 344 KB Correct! Number of queries: 11
6 Correct 1 ms 344 KB Correct! Number of queries: 13
7 Correct 2 ms 344 KB Correct! Number of queries: 300
8 Correct 2 ms 344 KB Correct! Number of queries: 300
9 Correct 3 ms 344 KB Correct! Number of queries: 300
10 Correct 2 ms 344 KB Correct! Number of queries: 300
11 Correct 1 ms 344 KB Correct! Number of queries: 200
12 Correct 2 ms 344 KB Correct! Number of queries: 300
13 Correct 2 ms 344 KB Correct! Number of queries: 200
14 Correct 2 ms 344 KB Correct! Number of queries: 300
15 Correct 2 ms 344 KB Correct! Number of queries: 300
16 Correct 2 ms 344 KB Correct! Number of queries: 300
17 Correct 31 ms 436 KB Correct! Number of queries: 1700
18 Correct 27 ms 444 KB Correct! Number of queries: 1600
19 Correct 28 ms 436 KB Correct! Number of queries: 1700
20 Correct 29 ms 444 KB Correct! Number of queries: 1700
21 Correct 29 ms 440 KB Correct! Number of queries: 1700
22 Correct 28 ms 440 KB Correct! Number of queries: 1700
23 Correct 31 ms 436 KB Correct! Number of queries: 1700
24 Correct 30 ms 444 KB Correct! Number of queries: 1700
25 Correct 30 ms 444 KB Correct! Number of queries: 1700
26 Correct 31 ms 440 KB Correct! Number of queries: 1700