oj.uz

답안 #1117048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117048 2024-11-22T19:24:19 Z pedroslrey CEOI16_icc (CEOI16_icc) C++17
61 / 100
 139 ms 760 KB 
#include <bits/stdc++.h>
#include "icc.h"

using namespace std;

void run(int n) {
	srand(time(0));
	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> xs, ys;
		while (true) {
			vector<int> as, bs;
			for (int i = 0; i < x; ++i)
				if (rand()%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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 592 KB Ok! 99 queries used.
2 Correct 6 ms 592 KB Ok! 121 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 592 KB Ok! 563 queries used.
2 Correct 40 ms 760 KB Ok! 834 queries used.
3 Correct 39 ms 592 KB Ok! 827 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 640 KB Ok! 1575 queries used.
2 Correct 134 ms 760 KB Ok! 2158 queries used.
3 Correct 130 ms 592 KB Ok! 1718 queries used.
4 Correct 129 ms 640 KB Ok! 1753 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 640 KB Ok! 1738 queries used.
2 Correct 108 ms 592 KB Ok! 1692 queries used.
3 Correct 116 ms 592 KB Ok! 1848 queries used.
4 Correct 106 ms 592 KB Ok! 1622 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 760 KB Too many queries! 1857 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 139 ms 592 KB Too many queries! 1964 out of 1625
2 Halted 0 ms 0 KB -