oj.uz

Submission #1117053

# Submission time Handle Problem Language Result Execution time Memory
1117053 2024-11-22T19:33:31 Z pedroslrey ICC (CEOI16_icc) C++17
61 / 100
 137 ms 760 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

void run(int n) {
	vector<vector<int>> comps(n);
	vector<int> rep(n);
	for (int i = 0; i < n; ++i) {
		comps[i].push_back(i);
		rep[i] = i;
	}

	auto comp_query = [&](vector<int> &as, vector<int> &bs) {
		static int a[100], b[100];

		int cnta = 0;
		for (int u: as)
			for (int e: comps[u])
				a[cnta++] = e + 1;

		int cntb = 0;
		for (int u: bs)
			for (int e: comps[u])
				b[cntb++] = e + 1;

		return query(cnta, cntb, a, b);
	};

	auto vec_query = [&](vector<int> &as, vector<int> &bs) {
		static int a[100], b[100];

		int cnta = 0;
		for (int u: as)
			a[cnta++] = u + 1;

		int cntb = 0;
		for (int u: bs)
			b[cntb++] = u + 1;

		return query(cnta, cntb, a, b);
	};

	int cnt = 0;
	auto turn = [&](int x) {
		static mt19937 rng(time(0));
		vector<int> xs, ys;
		while (true) {
			++cnt;
			vector<int> as, bs;
			for (int i = 0; i < x; ++i)
				if (rng()%2) as.push_back(i);
				else bs.push_back(i);

			if (comp_query(as, bs)) {
				for (int l: as)
					for (int u: comps[l])
						xs.push_back(u);

				for (int r: bs)
					for (int u: comps[r])
						ys.push_back(u);
				break;
			}
		}

		// cerr << "SETS:\n";
		// for (int x: xs)
		// 	cerr << x << " ";
		// cerr << "\n";
		// for (int y: ys)
		// 	cerr << y << " ";
		// cerr << "\n";

		int l = 0, r = xs.size();
		while (l < r - 1) {
			int m = (l + r)/2;

			vector<int> qs;
			for (int i = l; i < m; ++i)
				qs.push_back(xs[i]);

			if (vec_query(qs, ys)) r = m;
			else l = m;
		}

		int u = xs[l];

		l = 0, r = ys.size();
		while (l < r - 1) {
			int m = (l + r)/2;

			vector<int> qs;
			for (int i = l; i < m; ++i)
				qs.push_back(ys[i]);

			if (vec_query(qs, xs)) r = m;
			else l = m;
		}

		int v = ys[l];

		return make_pair(u, v);
	};

	auto swap_comps = [&](int a, int b) {
		swap(comps[a], comps[b]);

		for (int u: comps[a]) rep[u] = a;
		for (int v: comps[b]) rep[v] = b;
	};

	for (int i = n; i > 1; --i) {
		auto [u, v] = turn(i);

		swap_comps(rep[u], i - 1);
		swap_comps(rep[v], i - 2);

		for (int u: comps[i-1]) {
			comps[i-2].push_back(u);
			rep[u] = i-2;
		}

		setRoad(u + 1, v + 1);
	}

	assert(cnt/n <= 4);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 592 KB Ok! 103 queries used.
2 Correct 5 ms 640 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 592 KB Ok! 536 queries used.
2 Correct 45 ms 628 KB Ok! 880 queries used.
3 Correct 36 ms 592 KB Ok! 801 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 592 KB Ok! 1525 queries used.
2 Correct 129 ms 592 KB Ok! 2179 queries used.
3 Correct 110 ms 632 KB Ok! 1753 queries used.
4 Correct 105 ms 640 KB Ok! 1726 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 592 KB Ok! 1722 queries used.
2 Correct 102 ms 644 KB Ok! 1760 queries used.
3 Correct 108 ms 760 KB Ok! 1876 queries used.
4 Correct 96 ms 640 KB Ok! 1663 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 632 KB Too many queries! 1888 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 592 KB Too many queries! 1965 out of 1625
2 Halted 0 ms 0 KB -