oj.uz

Submission #365416

# Submission time Handle Problem Language Result Execution time Memory
365416 2021-02-11T15:49:31 Z Mlxa Mouse (info1cup19_mouse) C++14
88.5385 / 100
 172 ms 1772 KB 
#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1000;

int n;
int p[N];
int c[N][N];
bool b[N][N];
int bc[N];
int kn[N];

mt19937 rnd;

int query(vector<int>);
int qcnt = 0;

void block(int i, int j) {
	if (b[i][j]) {
		return;
	}
	b[i][j] = true;
	++bc[i];
	if (bc[i] == n - 1) {
		kn[i] = 1;
		while (b[i][kn[i]]) {
			++kn[i];
		}
		for (int ii = 0; ii < n; ++ii) {
			if (ii != i) {
				block(ii, kn[i]);
			}
		}
	}
}

bool bad(vector<int> q) {
	for (int i = 0; i < (int)q.size(); ++i) {
		if (q[i] == kn[i]) {
			return true;
		}
	}
	return false;
}

bool test(vector<int> q, int i, int j) {
	assert(query(q) == 0);
	j = (int)(find(all(q), j) - q.begin());
	swap(q[i], q[j]);
	vector<int> to;
	for (int t = 0; t < n; ++t) {
		if (t == i || t == j) {
			continue;
		}
		to.push_back(t);
	}
	shuffle(all(to), rnd);
	to.resize(n <= 50 ? 2 : 3);
	bool res = false;
	for (int t : to) {
		swap(q[j], q[t]);
		if (!query(q)) {
			res = true;
		}
		swap(q[j], q[t]);
		if (res) {
			break;
		}
	}
	swap(q[i], q[j]);
	return res;
}

void solve(int _n) {
	n = _n;
	vector<int> q(n);
	iota(all(q), 1);
	for (int it = 1; it < 7 * n; ++it) {
		int cur = query(q);
		if (cur == n) {
			return;
		}
		if (cur > 1) {
			for (int i = 0; i < n; ++i) {
				c[i][q[i]] += cur;
			}
		} else if (!cur) {
			for (int i = 0; i < n; ++i) {
				block(i, q[i]);
			}
		}
		shuffle(all(q), rnd);
		while (bad(q)) {
			shuffle(all(q), rnd);
		}
		if (*min_element(bc, bc + n) == n - 1) {
			break;
		}
	}
	while (query(q)) {
		shuffle(all(q), rnd);
	}
	vector<int> ord(n);
	iota(all(ord), 0);
	for (int i : ord) {
		priority_queue<pair<int, int>> qu;
		for (int j = 1; j <= n; ++j) {
			if (!b[i][j]) {
				qu.emplace(c[i][j], j);
			}
		}
		kn[i] = -1;
		while (qu.size() > 1) {
			int j = qu.top().y;
			if (!test(q, i, j)) {
				kn[i] = j;
				break;
			} else {
				qu.pop();
			}
		}
		if (kn[i] == -1) {
			kn[i] = qu.top().y;
		}
		for (int j = 1; j <= n; ++j) {
			if (j != kn[i]) {
				block(i, j);
			}
		}
	}
	q.assign(kn, kn + n);
	assert(query(q) == n);
}

#ifdef LC
int query(vector<int> q) {
	++qcnt;
	int cnt = 0;
	for (int i = 0; i < (int)q.size(); ++i) {
		cnt += p[i] == q[i];
	}
	return cnt;
}
signed main() {
	assert(freopen("input.txt", "r", stdin));
	int _n;
	cin >> _n;
	for (int i = 0; i < _n; ++i) {
		cin >> p[i];
	}
	solve(_n);
	return 0;
}
#endif

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 36
2 Correct 1 ms 364 KB Correct! Number of queries: 3
3 Correct 1 ms 364 KB Correct! Number of queries: 32
4 Correct 1 ms 364 KB Correct! Number of queries: 36
5 Correct 1 ms 364 KB Correct! Number of queries: 26
6 Correct 1 ms 364 KB Correct! Number of queries: 17

Subtask #2
35.000014 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 36
2 Correct 1 ms 364 KB Correct! Number of queries: 3
3 Correct 1 ms 364 KB Correct! Number of queries: 32
4 Correct 1 ms 364 KB Correct! Number of queries: 36
5 Correct 1 ms 364 KB Correct! Number of queries: 26
6 Correct 1 ms 364 KB Correct! Number of queries: 17
7 Correct 8 ms 620 KB Correct! Number of queries: 500
8 Correct 10 ms 620 KB Correct! Number of queries: 500
9 Correct 8 ms 620 KB Correct! Number of queries: 500
10 Correct 8 ms 620 KB Correct! Number of queries: 500
11 Correct 7 ms 492 KB Correct! Number of queries: 400
12 Correct 7 ms 620 KB Correct! Number of queries: 500
13 Correct 7 ms 620 KB Correct! Number of queries: 500
14 Correct 8 ms 516 KB Correct! Number of queries: 500
15 Correct 12 ms 620 KB Correct! Number of queries: 500
16 Correct 9 ms 620 KB Correct! Number of queries: 500

Subtask #3
40.538484 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 36
2 Correct 1 ms 364 KB Correct! Number of queries: 3
3 Correct 1 ms 364 KB Correct! Number of queries: 32
4 Correct 1 ms 364 KB Correct! Number of queries: 36
5 Correct 1 ms 364 KB Correct! Number of queries: 26
6 Correct 1 ms 364 KB Correct! Number of queries: 17
7 Correct 8 ms 620 KB Correct! Number of queries: 500
8 Correct 10 ms 620 KB Correct! Number of queries: 500
9 Correct 8 ms 620 KB Correct! Number of queries: 500
10 Correct 8 ms 620 KB Correct! Number of queries: 500
11 Correct 7 ms 492 KB Correct! Number of queries: 400
12 Correct 7 ms 620 KB Correct! Number of queries: 500
13 Correct 7 ms 620 KB Correct! Number of queries: 500
14 Correct 8 ms 516 KB Correct! Number of queries: 500
15 Correct 12 ms 620 KB Correct! Number of queries: 500
16 Correct 9 ms 620 KB Correct! Number of queries: 500
17 Correct 169 ms 1772 KB Correct! Number of queries: 3500
18 Correct 161 ms 1600 KB Correct! Number of queries: 3300
19 Correct 137 ms 1516 KB Correct! Number of queries: 3100
20 Correct 158 ms 1644 KB Correct! Number of queries: 3500
21 Correct 154 ms 1516 KB Correct! Number of queries: 3400
22 Correct 142 ms 1592 KB Correct! Number of queries: 3200
23 Correct 161 ms 1612 KB Correct! Number of queries: 3300
24 Correct 158 ms 1652 KB Correct! Number of queries: 3400
25 Correct 172 ms 1772 KB Correct! Number of queries: 3500
26 Correct 169 ms 1652 KB Correct! Number of queries: 3400