oj.uz

Submission #24913

# Submission time Handle Problem Language Result Execution time Memory
24913 2017-06-17T05:48:50 Z nibnalin ICC (CEOI16_icc) C++14
90 / 100
 149 ms 2228 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#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);
}

inline int left(int node) { return (node<<1); }
inline int right(int node) { return (node<<1)+1; }

int build(int node, int L, int R, int ht)
{
	if(L == R) return ht;
	else
	{
		int mid = (L+R)/2;

		for(int i = L;i <= mid;i++)
		{
			for(auto it: vec[i]) Q[ht].first.push_back(it);
		}
		for(int i = mid+1;i <= R;i++)
		{
			for(auto it: vec[i]) Q[ht].second.push_back(it);
		}
		return max(build(left(node), L, mid, ht+1), build(right(node), mid+1, R, 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()
{
	for(int i = 0;i < n;i++) vec[i].clear();
	for(int i = 0;i < n;i++) vec[root(i)].push_back(i);

	int maxht = build(1, 0, n-1, 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)
{
	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 2088 KB Ok! 111 queries used.
2 Correct 6 ms 2092 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2096 KB Ok! 567 queries used.
2 Correct 43 ms 2096 KB Ok! 656 queries used.
3 Correct 39 ms 2092 KB Ok! 667 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 2220 KB Ok! 1351 queries used.
2 Correct 126 ms 2224 KB Ok! 1619 queries used.
3 Correct 113 ms 2228 KB Ok! 1368 queries used.
4 Correct 129 ms 2220 KB Ok! 1563 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2224 KB Ok! 1388 queries used.
2 Correct 146 ms 2224 KB Ok! 1399 queries used.
3 Correct 139 ms 2228 KB Ok! 1623 queries used.
4 Correct 113 ms 2220 KB Ok! 1353 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2224 KB Ok! 1621 queries used.
2 Correct 133 ms 2224 KB Ok! 1641 queries used.
3 Correct 133 ms 2228 KB Ok! 1645 queries used.
4 Correct 146 ms 2224 KB Ok! 1617 queries used.
5 Correct 126 ms 2224 KB Ok! 1512 queries used.
6 Correct 129 ms 2228 KB Ok! 1619 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 2224 KB Too many queries! 1634 out of 1625
2 Halted 0 ms 0 KB -