oj.uz

Submission #1117049

# Submission time Handle Problem Language Result Execution time Memory
1117049 2024-11-22T19:29:10 Z pedroslrey ICC (CEOI16_icc) C++17
61 / 100
 140 ms 816 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) {
		static mt19937 rng(time(0));
		vector<int> xs, ys;
		while (true) {
			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);

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

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 592 KB Ok! 550 queries used.
2 Correct 41 ms 760 KB Ok! 865 queries used.
3 Correct 41 ms 636 KB Ok! 818 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 764 KB Ok! 1589 queries used.
2 Correct 135 ms 652 KB Ok! 2173 queries used.
3 Correct 122 ms 592 KB Ok! 1777 queries used.
4 Correct 112 ms 816 KB Ok! 1748 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 592 KB Ok! 1760 queries used.
2 Correct 112 ms 656 KB Ok! 1771 queries used.
3 Correct 140 ms 668 KB Ok! 1920 queries used.
4 Correct 127 ms 592 KB Ok! 1682 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 656 KB Too many queries! 1867 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 644 KB Too many queries! 1951 out of 1625
2 Halted 0 ms 0 KB -