oj.uz

Submission #650652

# Submission time Handle Problem Language Result Execution time Memory
650652 2022-10-14T12:27:54 Z ymm ICC (CEOI16_icc) C++17
100 / 100
 127 ms 628 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Ok! 114 queries used.
2 Correct 7 ms 468 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 508 KB Ok! 640 queries used.
2 Correct 31 ms 436 KB Ok! 558 queries used.
3 Correct 34 ms 512 KB Ok! 570 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 508 KB Ok! 1575 queries used.
2 Correct 116 ms 508 KB Ok! 1436 queries used.
3 Correct 124 ms 496 KB Ok! 1527 queries used.
4 Correct 118 ms 500 KB Ok! 1528 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 504 KB Ok! 1490 queries used.
2 Correct 119 ms 520 KB Ok! 1496 queries used.
3 Correct 116 ms 508 KB Ok! 1467 queries used.
4 Correct 124 ms 504 KB Ok! 1537 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 556 KB Ok! 1439 queries used.
2 Correct 111 ms 628 KB Ok! 1441 queries used.
3 Correct 115 ms 500 KB Ok! 1480 queries used.
4 Correct 119 ms 468 KB Ok! 1500 queries used.
5 Correct 121 ms 496 KB Ok! 1561 queries used.
6 Correct 116 ms 436 KB Ok! 1539 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 512 KB Ok! 1472 queries used.
2 Correct 111 ms 508 KB Ok! 1436 queries used.