oj.uz

Submission #1116990

# Submission time Handle Problem Language Result Execution time Memory
1116990 2024-11-22T17:51:24 Z pedroslrey ICC (CEOI16_icc) C++17
90 / 100
 125 ms 828 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);
	};

	auto turn = [&](int x) {
		vector<int> perm;
		for (int k = 0; k <= __lg(x); ++k)
			perm.push_back(k);

		random_shuffle(perm.begin(), perm.end());

		vector<int> xs, ys;
		for (int k: perm) {
			vector<int> as, bs;
			for (int i = 0; i < x; ++i)
				if (i & (1 << k)) 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);

		cerr << "REP: ";
		for (int r: rep)
			cerr << r << " ";
		cerr << "\n";
	}
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 592 KB Ok! 545 queries used.
2 Correct 36 ms 760 KB Ok! 698 queries used.
3 Correct 33 ms 764 KB Ok! 688 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 648 KB Ok! 1447 queries used.
2 Correct 124 ms 660 KB Ok! 1716 queries used.
3 Correct 102 ms 644 KB Ok! 1624 queries used.
4 Correct 102 ms 644 KB Ok! 1575 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 592 KB Ok! 1575 queries used.
2 Correct 115 ms 656 KB Ok! 1590 queries used.
3 Correct 106 ms 652 KB Ok! 1660 queries used.
4 Correct 105 ms 648 KB Ok! 1509 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 592 KB Ok! 1671 queries used.
2 Correct 115 ms 648 KB Ok! 1689 queries used.
3 Correct 107 ms 652 KB Ok! 1703 queries used.
4 Correct 104 ms 592 KB Ok! 1651 queries used.
5 Correct 101 ms 760 KB Ok! 1514 queries used.
6 Correct 103 ms 828 KB Ok! 1594 queries used.

Subtask #6
0 / 10.0

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