oj.uz

Submission #253628

# Submission time Handle Problem Language Result Execution time Memory
253628 2020-07-28T13:17:37 Z tonowak Carnival (CEOI14_carnival) C++14
0 / 100
 1000 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() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	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);
		cout << size(indices) << ' ';
		for(int i : indices)
			cout << i + 1 << ' ';
		cout << '\n' << flush;
		int ret;
		cin >> ret;
		return ret == size(indices);
	};

	function<bool (vector<int>)> solve = [&](vector<int> indices) {
		debug(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((size(half) + 1) / 2);
				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);

	cout << "0 ";
	REP(v, n)
		cout << color[v] + 1 << ' ';
	cout << '\n' << flush;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3074 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3055 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3093 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -