oj.uz

Submission #96035

# Submission time Handle Problem Language Result Execution time Memory
96035 2019-02-05T10:22:21 Z youngyojun ICC (CEOI16_icc) C++11
100 / 100
 144 ms 696 KB 
#include "icc.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef pair<int, int> pii;
mt19937 mtrd(time(0));

int askA[105], askB[105];
bool ask(vector<int> &A, vector<int> &B) {
	int a = 0, b = 0;
	for(int v : A) askA[a++] = v;
	for(int v : B) askB[b++] = v;
	return query(a, b, askA, askB);
}

vector<int> UV[105];
int ud[105];

int N;

int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) {
	a = uf(a); b = uf(b);
	if(a == b) return;
	for(int v : UV[b]) UV[a].eb(v);
	UV[b].clear();
	ud[b] = a;
}

void run() {
	vector<int> LV;
	for(int i = 1; i <= N; i++)
		if(uf(i) == i) LV.eb(i);
	shuffle(allv(LV), mtrd);
	int n = sz(LV), x = 0;
	for(int k = 1;; k <<= 1) {
		bool flag = false;
		for(int i = 0; i < n; i++) {
			if(n <= (i^x^k)) continue;
			flag = true;
			break;
		}
		if(!flag) break;
		vector<int> AV, BV;
		for(int i = 0; i < n; i++) {
			auto &V = (i&k) ? AV : BV;
			for(int v : UV[LV[i]]) V.eb(v);
		}
		if(AV.empty() || BV.empty()) continue;
		if(ask(AV, BV)) x |= k;
	}

	vector<pii> EV;
	for(int i = 0, j; i < n; i++) {
		j = i^x;
		if(j <= i || n <= j) continue;
		EV.eb(i, j);
	}
	shuffle(allv(EV), mtrd);
	for(; 1 < sz(EV);) {
		vector<pii> LE, RE;
		int e = sz(EV), m = e >> 1;
		for(int i = 0; i < m; i++) LE.eb(EV[i]);
		for(int i = m; i < e; i++) RE.eb(EV[i]);
		vector<int> AV, BV;
		for(auto &ed : LE) {
			for(int v : UV[LV[ed.first]]) AV.eb(v);
			for(int v : UV[LV[ed.second]]) BV.eb(v);
		}
		swap(EV, ask(AV, BV) ? LE : RE);
	}

	vector<int> AT, BT;
	for(int v : UV[LV[EV[0].first]]) AT.eb(v);
	for(int v : UV[LV[EV[0].second]]) BT.eb(v);
	shuffle(allv(AT), mtrd);
	shuffle(allv(BT), mtrd);
	for(; 1 < sz(AT);) {
		vector<int> AL, AR;
		int e = sz(AT), m = e >> 1;
		for(int i = 0; i < m; i++) AL.eb(AT[i]);
		for(int i = m; i < e; i++) AR.eb(AT[i]);
		swap(AT, ask(AL, BT) ? AL : AR);
	}
	for(; 1 < sz(BT);) {
		vector<int> BL, BR;
		int e = sz(BT), m = e >> 1;
		for(int i = 0; i < m; i++) BL.eb(BT[i]);
		for(int i = m; i < e; i++) BR.eb(BT[i]);
		swap(BT, ask(AT, BL) ? BL : BR);
	}

	{
		int a = AT[0], b = BT[0];
		uf(a, b);
		setRoad(a, b);
	}
}

void run(int _N) {
	N = _N;
	iota(ud, ud+N+1, 0);
	for(int i = 1; i <= N; i++) UV[i].eb(i);
	for(int lq = 1; lq < N; lq++) run();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 113 queries used.
2 Correct 8 ms 504 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 504 KB Ok! 608 queries used.
2 Correct 37 ms 504 KB Ok! 490 queries used.
3 Correct 40 ms 568 KB Ok! 561 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 696 KB Ok! 1545 queries used.
2 Correct 126 ms 504 KB Ok! 1195 queries used.
3 Correct 142 ms 620 KB Ok! 1525 queries used.
4 Correct 139 ms 504 KB Ok! 1495 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 632 KB Ok! 1497 queries used.
2 Correct 139 ms 504 KB Ok! 1497 queries used.
3 Correct 133 ms 632 KB Ok! 1457 queries used.
4 Correct 144 ms 568 KB Ok! 1526 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 636 KB Ok! 1379 queries used.
2 Correct 140 ms 636 KB Ok! 1445 queries used.
3 Correct 133 ms 504 KB Ok! 1353 queries used.
4 Correct 142 ms 572 KB Ok! 1478 queries used.
5 Correct 139 ms 504 KB Ok! 1517 queries used.
6 Correct 144 ms 632 KB Ok! 1472 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 504 KB Ok! 1379 queries used.
2 Correct 128 ms 504 KB Ok! 1223 queries used.