Submission #870011

#	Time	Username	Problem	Language	Result	Execution time	Memory
870011		rainboy	Mouse (info1cup19_mouse)	C++17	100 / 100	31 ms	444 KiB

mouse

#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 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49