Submission #650652

#	Time	Username	Problem	Language	Result	Execution time	Memory
650652		ymm	ICC (CEOI16_icc)	C++17	100 / 100	127 ms	628 KiB

icc

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#ifdef local
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
#else
#include "icc.h"
#endif

const int N = 100;
vector<int> A[N];
int col[N];
int n;

bool query_col(vector<int> a)
{
	set<int> s(a.begin(), a.end());
	vector<int> x, y;
	Loop (i,0,n) {
		if (s.count(col[i]))
			x.push_back(i+1);
		else
			y.push_back(i+1);
	}
	if (x.empty() || y.empty())
		return 0;
	return query(x.size(), y.size(), &x[0], &y[0]);
}

bool query_range(vector<int> a, vector<int> b, int l, int r)
{
	vector<int> v, u;
	Loop (i,l,r)
		v.push_back(a[i]+1);
	Loop (i,0,b.size())
		u.push_back(b[i]+1);
	return query(v.size(), u.size(), &v[0], &u[0]);
}

vector<int> dfs(int v, int p, int c)
{
	vector<int> ans = {v};
	if (c >= 0)
		col[v] = c;
	for (int u : A[v]) {
		if (u != p) {
			auto tmp = dfs(u, v, c);
			for (int x : tmp)
				ans.push_back(x);
		}
	}
	return ans;
}

int bin_search(vector<int> a, vector<int> b)
{
	int l = 0, r = a.size()-1;
	while (l < r) {
		int mid = (l+r)/2;
		if (query_range(a, b, l, mid+1))
			r = mid;
		else
			l = mid+1;
	}
	return l;
}

vector<int> cv[N];
int cv_len;

void find_next()
{
	cv_len = 0;
	memset(col, -1, sizeof(col));
	Loop (i,0,n) {
		if (col[i] == -1) {
			cv[cv_len] = dfs(i, -1, cv_len);
			++cv_len;
		}
	}
	int lg = __lg(cv_len-1)+1;
	int delta = 0, first = 0;
	Loop (i,0,lg) {
		vector<int> v;
		Loop (j,0,cv_len)
			if (j & (1<<i))
				v.push_back(j);
		if (query_col(v))
			delta ^= (1<<i);
	}
	int fbit = __builtin_ctz(delta);
	first ^= 1 << fbit;
	Loop (i,0,lg) {
		if (i == fbit)
			continue;
		vector<int> v;
		Loop (j,0,cv_len)
			if ((j & (1<<i)) && (j & (1<<fbit)))
				v.push_back(j);
		if (query_col(v))
			first ^= (1<<i);
	}
	int second = first ^ delta;
	vector<int> a = cv[first], b = cv[second];
	int v = a[bin_search(a, b)];
	int u = b[bin_search(b, a)];
	setRoad(v+1, u+1);
	A[v].push_back(u);
	A[u].push_back(v);
}

void run(int n)
{
	::n = n;
	Loop (i,0,n-1)
		find_next();
}

#ifdef local
int query(int size_a, int size_b, int a[], int b[])
{
	cout << "query\n";
	Loop (i,0,size_a)
		cout << a[i] << ' ';
	cout << '\n';
	Loop (i,0,size_b)
		cout << b[i] << ' ';
	cout << '\n';
	int ans;
	cin >> ans;
	return ans;
}

void setRoad(int a, int b)
{
	cout << "setRoad\n";
	cout << a << ' ' << b << '\n';
	cout << "continue? ";
	char c;
	cin >> c;
	if (c != 'y')
		exit(0);
}

int main()
{
	int n;
	cin >> n;
	run(n);
}
#endif

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10