oj.uz

Submission #24915

# Submission time Handle Problem Language Result Execution time Memory
24915 2017-06-17T06:00:16 Z nibnalin ICC (CEOI16_icc) C++14
100 / 100
 169 ms 2228 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include "icc.h"
using namespace std;

const int maxn = 105, inf = int(1e9)+5;

int n, P[maxn];
pair<vector<int>, vector<int>> Q[10];
vector<int> vec[maxn];

inline int root(int node)
{
	return ((P[node] == node)?node:(P[node] = root(P[node])));
}

void dsu(int x, int y)
{
	x = root(x), y = root(y);
	P[y] = x;
}

/*void setRoad(int a, int b)
{
	cout << "SETROAD " << a << " " << b << "\n";
}

int query(int n, int m, int* a, int* b)
{
	cout << "ASKQUERY\n";
	cout << n << ": ";
	for(int i = 0;i < n;i++) cout << a[i] << " ";
	cout << "\n";
	cout << m << ": ";
	for(int i = 0;i < m;i++) cout << b[i] << " ";
	cout << "\n";
	int ret;
	cin >> ret;
	return ret;
}*/

bool ask(pair<vector<int>, vector<int>>& A)
{
	int a_sz = int(A.first.size()), b_sz = int(A.second.size());
	int q1[a_sz], q2[b_sz];
	for(int i = 0;i < a_sz;i++) q1[i] = A.first[i]+1;
	for(int i = 0;i < b_sz;i++) q2[i] = A.second[i]+1;
	return query(a_sz, b_sz, q1, q2);
}

int build(vector<int> todo, int ht)
{
	if(int(todo.size()) == 1) return ht;
	else
	{
		int mid = (int(todo.size())-1)/2;
		random_shuffle(todo.begin(), todo.end());
		vector<int> lef, righ;

		for(int i = 0;i <= mid;i++)
		{
			lef.push_back(todo[i]);
			for(auto it: vec[todo[i]]) Q[ht].first.push_back(it);
		}
		for(int i = mid+1;i < int(todo.size());i++)
		{
			righ.push_back(todo[i]);
			for(auto it: vec[todo[i]]) Q[ht].second.push_back(it);
		}
		return max(build(lef, ht+1), build(righ, ht+1));
	}
}

pair<int, int> precise(pair<vector<int>, vector<int>>& A)
{
	int L = 0, R = int(A.first.size())-2, ans = int(A.first.size())-1;
	while(L <= R)
	{
		int mid = (L+R)/2;
		pair<vector<int>, vector<int>> yolo;
		yolo.second = A.second;
		for(int i = 0;i <= mid;i++) yolo.first.push_back(A.first[i]);
		if(ask(yolo))
		{
			ans = min(ans, mid);
			R = mid-1;
		}
		else L = mid+1;
	}
	pair<int, int> ret = {A.first[ans], inf};
	swap(A.first, A.second);
	L = 0, R = int(A.first.size())-2, ans = int(A.first.size())-1;
	while(L <= R)
	{
		int mid = (L+R)/2;
		pair<vector<int>, vector<int>> yolo;
		yolo.second = A.second;
		for(int i = 0;i <= mid;i++) yolo.first.push_back(A.first[i]);
		if(ask(yolo))
		{
			ans = min(ans, mid);
			R = mid-1;
		}
		else L = mid+1;
	}
	ret.second = A.first[ans];
	swap(A.first, A.second);
	return ret;
}

void solve()
{
	vector<int> complet;
	for(int i = 0;i < n;i++) vec[i].clear();
	for(int i = 0;i < n;i++)
	{
		vec[root(i)].push_back(i);
		if(i == root(i)) complet.push_back(root(i));
	}

	int maxht = build(complet, 0);

	pair<int, int> res;
	for(int i = 0;i < maxht;i++)
	{
		if(Q[i].first.empty() || Q[i].second.empty()) continue;
		if(ask(Q[i]))
		{
			res = precise(Q[i]);
			break;
		}
	}
	dsu(res.first, res.second);
	setRoad(res.first+1, res.second+1);

	for(int i = 0;i < maxht;i++) Q[i].first.clear(), Q[i].second.clear();
}

void run(int N)
{
	srand(1234567890);
	n = N;
	for(int i = 0;i < n;i++) P[i] = i;
	for(int i = 1;i < n;i++) solve();
}

/*int main(void)
{
	int v;
	cin >> v;

	run(v);
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2096 KB Ok! 99 queries used.
2 Correct 6 ms 2088 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2092 KB Ok! 543 queries used.
2 Correct 39 ms 2096 KB Ok! 639 queries used.
3 Correct 46 ms 2088 KB Ok! 663 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 2220 KB Ok! 1472 queries used.
2 Correct 139 ms 2224 KB Ok! 1552 queries used.
3 Correct 139 ms 2220 KB Ok! 1575 queries used.
4 Correct 139 ms 2228 KB Ok! 1534 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2224 KB Ok! 1487 queries used.
2 Correct 136 ms 2224 KB Ok! 1522 queries used.
3 Correct 163 ms 2228 KB Ok! 1632 queries used.
4 Correct 136 ms 2224 KB Ok! 1439 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 2224 KB Ok! 1614 queries used.
2 Correct 146 ms 2224 KB Ok! 1622 queries used.
3 Correct 143 ms 2224 KB Ok! 1605 queries used.
4 Correct 156 ms 2228 KB Ok! 1626 queries used.
5 Correct 143 ms 2220 KB Ok! 1522 queries used.
6 Correct 169 ms 2224 KB Ok! 1626 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 2224 KB Ok! 1599 queries used.
2 Correct 143 ms 2224 KB Ok! 1590 queries used.