oj.uz

Submission #129967

# Submission time Handle Problem Language Result Execution time Memory
129967 2019-07-13T16:44:38 Z keko37 ICC (CEOI16_icc) C++14
0 / 100
 5 ms 504 KB 
#include<bits/stdc++.h>
#include "icc.h"

using namespace std;

const int MAXN = 105;

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

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, fin[i]);
			ubaci(1, fin[i] ^ comp);
		}
		if (pitaj()) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	return make_pair(fin[lo], 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);
	}
	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);
		for (auto r : v[y]) v[x].push_back(r);
		curr.erase(find(curr.begin(), curr.end(), y));
	}
}

Compilation message

icc.cpp: In function 'bool pitaj()':
icc.cpp:14: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:15: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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -