oj.uz

Submission #129979

# Submission time Handle Problem Language Result Execution time Memory
129979 2019-07-13T17:05:07 Z keko37 ICC (CEOI16_icc) C++14
100 / 100
 152 ms 632 KB 
#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

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.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 504 KB Ok! 616 queries used.
2 Correct 38 ms 564 KB Ok! 455 queries used.
3 Correct 41 ms 560 KB Ok! 510 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 632 KB Ok! 1538 queries used.
2 Correct 119 ms 504 KB Ok! 1077 queries used.
3 Correct 145 ms 572 KB Ok! 1524 queries used.
4 Correct 148 ms 504 KB Ok! 1514 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 504 KB Ok! 1454 queries used.
2 Correct 142 ms 504 KB Ok! 1482 queries used.
3 Correct 152 ms 600 KB Ok! 1482 queries used.
4 Correct 150 ms 504 KB Ok! 1530 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 504 KB Ok! 1483 queries used.
2 Correct 152 ms 576 KB Ok! 1451 queries used.
3 Correct 137 ms 548 KB Ok! 1346 queries used.
4 Correct 144 ms 632 KB Ok! 1492 queries used.
5 Correct 146 ms 600 KB Ok! 1519 queries used.
6 Correct 148 ms 504 KB Ok! 1528 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 568 KB Ok! 1444 queries used.
2 Correct 131 ms 504 KB Ok! 1257 queries used.