oj.uz

Submission #253688

# Submission time Handle Problem Language Result Execution time Memory
253688 2020-07-28T14:09:49 Z tonowak Carnival (CEOI14_carnival) C++14
100 / 100
 23 ms 384 KB 
#include "bits/stdc++.h" // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

int main() {
	int n;
	cin >> n;
#ifdef LOCAL
	vector<int> ehh(n);
	for(int &x : ehh) {
		cin >> x;
		--x;
	}
#endif
	vector<int> lead(n);
	iota(lead.begin(), lead.end(), 0);
	function<int (int)> find = [&](int i) {
		if(i == lead[i])
			return i;
		return lead[i] = find(lead[i]);
	};

	auto merge = [&](int i, int j) {
		i = find(i);
		j = find(j);
		debug(i, j);
		assert(i != j);
		lead[i] = j;
	};

	auto rm_nonleaders = [&](vector<int> indices) {
		vector<int> ret;
		for(int i : indices)
			if(find(i) == i)
				ret.emplace_back(i);
		return ret;
	};

	auto ask = [&](vector<int> indices) {
		indices = rm_nonleaders(indices);
#ifdef LOCAL
		vector<bool> inside(n);
		for(int i : indices)
			inside[ehh[i]] = true;
		int ret = accumulate(inside.begin(), inside.end(), 0);
#else
		cout << size(indices) << ' ';
		for(int i : indices)
			cout << i + 1 << ' ';
		cout << '\n' << flush;
		int ret;
		cin >> ret;
#endif
		return ret == size(indices);
	};

	function<bool (vector<int>)> solve = [&](vector<int> indices) {
		if(size(indices) <= 1)
			return false;
		else if(size(indices) == 2) {
			debug(2);
			if(ask(indices))
				return false;
			merge(indices[0], indices[1]);
			return true;
		}
		else {
			int requests = 0;
			bool need_to_ask = true;
			while(need_to_ask == false or not ask(indices)) {
				++requests;

				vector<int> half = indices;
				shuffle(half.begin(), half.end(), rng);
				half.resize(max(2, (size(half) + 1) / 2));
				debug(indices, half);
				need_to_ask = solve(half);
				indices = rm_nonleaders(indices);
			}
			return requests > 0;
		}
	};

	vector<int> whole(n);
	iota(whole.begin(), whole.end(), 0);
	solve(whole);

	vector<int> color(n, -1);
	int color_cnt = 0;
	REP(i, n)
		if(color[find(i)] == -1)
			color[find(i)] = color[i] = color_cnt++;
		else 
			color[i] = color[find(i)];
	debug(color);

#ifdef LOCAL
	assert(color == ehh);
	cout << "OK\n";
#else
	cout << "0 ";
	REP(v, n)
		cout << color[v] + 1 << ' ';
	cout << '\n' << flush;
#endif
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 256 KB Output is correct
2 Correct 16 ms 256 KB Output is correct
3 Correct 8 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 9 ms 256 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 17 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 256 KB Output is correct
2 Correct 22 ms 256 KB Output is correct
3 Correct 11 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 9 ms 256 KB Output is correct
6 Correct 10 ms 256 KB Output is correct
7 Correct 21 ms 256 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Correct 13 ms 256 KB Output is correct
3 Correct 19 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 13 ms 256 KB Output is correct
6 Correct 17 ms 256 KB Output is correct
7 Correct 19 ms 256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 256 KB Output is correct
2 Correct 11 ms 256 KB Output is correct
3 Correct 13 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 20 ms 376 KB Output is correct
6 Correct 10 ms 256 KB Output is correct
7 Correct 23 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 256 KB Output is correct
2 Correct 19 ms 256 KB Output is correct
3 Correct 17 ms 256 KB Output is correct
4 Correct 17 ms 256 KB Output is correct
5 Correct 12 ms 256 KB Output is correct
6 Correct 18 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct