oj.uz

Submission #365389

# Submission time Handle Problem Language Result Execution time Memory
365389 2021-02-11T15:05:13 Z Mlxa Mouse (info1cup19_mouse) C++14
0 / 100
 1 ms 364 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>);

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;
}

void solve(int _n) {
	n = _n;
	vector<int> q(n);
	iota(all(q), 1);
	// for (int it = 0; it < 20 * n; ++it) {
	// 	int cur = query(q);
	// 	if (cur > 2) {
	// 		for (int i = 0; i < n; ++i) {
	// 			c[i][q[i]] += cur;
	// 		}
	// 	} else if (!cur) {
	// 		for (int i = 0; i < n; ++i) {
	// 			b[i][q[i]] = true;
	// 		}
	// 	}
	// 	shuffle(all(q), rnd);
	// }
	// for (int i = 0; i < n; ++i) {
	// 	vector<int> can;
	// 	for (int j = 1; j <= n; ++j) {
	// 		if (b[i][j]) {
	// 			;
	// 		} else {
	// 			can.push_back(c[i][j]);
	// 		}
	// 	}
	// 	if (c[i][p[i]] != *max_element(all(can))) {
	// 		cout << i << ": " << can.size() << " " << c[i][p[i]] << " / " << *max_element(all(can)) << endl;
	// 	}
	// }
	for (int it = 1; ; ++it) {
		int cur = query(q);
		if (cur > 2) {
			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) {
#ifdef LC
			cout << it << " queries" << endl;
#endif
			for (int i = 0; i < n; ++i) {
				int j = 1;
				while (b[i][j]) {
					++j;
				}
				cout << j << " ";
			}
			cout << endl;
			return;
		}
	}
}

#ifdef LC
int query(vector<int> q) {
	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
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 35
2 Runtime error 1 ms 364 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 35
2 Runtime error 1 ms 364 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Correct! Number of queries: 35
2 Runtime error 1 ms 364 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -