Submission #129979

#	Time	Username	Problem	Language	Result	Execution time	Memory
129979		keko37	ICC (CEOI16_icc)	C++14	100 / 100	152 ms	632 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"

using namespace std;

 
/*int query (int size_a, int size_b, int aa[], int bb[]) {
    for(int i = 0; i < size_a; i++) {
        cout << aa[i] << ' ';
    } cout << '\n';
    for(int i = 0; i < size_b; i++) {
        cout << bb[i] << ' ';
    } cout << '\n';
    int res; cin >> res; return res;
}

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

const int MAXN = 105;

int n, comp;
int a[MAXN], b[MAXN], rod[MAXN];
vector <int> q[2], v[MAXN], fin;

int pred (int x) {
	if (x == rod[x]) return x;
	return rod[x] = pred(rod[x]);
}

bool pitaj () {
	if (q[0].empty() || q[1].empty()) return 0;
	for (int i=0; i<q[0].size(); i++) a[i] = q[0][i];
	for (int i=0; i<q[1].size(); i++) b[i] = q[1][i];
	return query(q[0].size(), q[1].size(), a, b);
}

void ubaci (int ind, int x) {
	for (auto y : v[x]) q[ind].push_back(y);
}

pair <int, int> rjesi (vector <int> p) {
	int m = p.size();
	int ofs = 1, cnt = 0;
	while (ofs < m) {
		ofs *= 2;
		cnt++;
	}
	comp = 0;
	for (int bt = 0; bt < cnt; bt++) {
		q[0].clear(); q[1].clear();
		for (int i=0; i<m; i++) {
			if (i & (1 << bt)) ubaci(0, p[i]); else ubaci(1, p[i]);
		}
		if (pitaj()) comp += (1 << bt);
	}
	fin.clear();
	for (int i=0; i<m; i++) {
		if (i < (i ^ comp) && (i ^ comp) < m) fin.push_back(i);
	}
	int lo = 0, hi = (int)fin.size() - 1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		q[0].clear(); q[1].clear();
		for (int i = lo; i <= mid; i++) {
			ubaci(0, p[fin[i]]);
			ubaci(1, p[fin[i] ^ comp]);
		}
		if (pitaj()) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	return make_pair(p[fin[lo]], p[fin[lo] ^ comp]);
}

int nadi (int x, int y) {
	int lo = 0, hi = (int)v[x].size() - 1;
	q[0].clear(); q[1].clear();
	ubaci(1, y);
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		q[0].clear();
		for (int i = lo; i <= mid; i++) {
			q[0].push_back(v[x][i]);
		}
		if (pitaj()) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	return v[x][lo];
}

void run (int N) {
	n = N;
	vector <int> curr;
	for (int i=1; i<=n; i++) {
		v[i].push_back(i);
		curr.push_back(i);
		rod[i] = i;
	}
	while (curr.size() > 1) {
		pair <int, int> par = rjesi(curr);
		int x = nadi(par.first, par.second);
		int y = nadi(par.second, par.first);
		setRoad(x, y);
		x = pred(x); y = pred(y);
		rod[y] = x;
		for (auto r : v[y]) v[x].push_back(r);
		curr.erase(find(curr.begin(), curr.end(), y));
	}
}

/*int main () {
    int nn; cin >> nn;
    run(nn);
}*/

Compilation message (stderr)

icc.cpp: In function 'bool pitaj()':
icc.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<q[0].size(); i++) a[i] = q[0][i];
                ~^~~~~~~~~~~~
icc.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<q[1].size(); i++) b[i] = q[1][i];
                ~^~~~~~~~~~~~

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