oj.uz

Submission #476241

# Submission time Handle Problem Language Result Execution time Memory
476241 2021-09-25T14:32:41 Z Hamed5001 Carnival (CEOI14_carnival) C++14
0 / 100
 1 ms 200 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 150;
vector<int> ans(mxN);

struct DSU {
	int N;
	vector<int> P;

	DSU(int N) : N(N) {
		P.resize(N);
		for (int i = 0; i < N; i++)
			P[i] = i;
	}

	int get_parent(int a) {
		return P[a] = (P[a] == a ? a : get_parent(P[a]));
	}

	void unite(int a, int b) {
		a = get_parent(a);
		b = get_parent(b);
		P[a] = b;
	}
};

DSU d(mxN);

bool query(int l, int r, int x) {
	set<int> st;
	cout << r - l + 2 << ' ';
	for (int i = l; i <= r; i++) {
		st.insert(d.get_parent(i));
		cout << d.get_parent(i)+1 << ' ';
	}
	st.insert(x);
	cout << x+1 << endl;
	int res;
	cin >> res;
	return res == st.size();
}

void solve() {
	int N, id = 1;
	cin >> N;	  

	ans[0] = id++;

	for (int i = 1; i < N; i++) {
		if (query(0, i-1, i)) {
			ans[i] = id++;
			continue;
		}

		int l = 0, r = i-1, mid;
		while(l < r) {
			mid = (l+r)>>1;
			if (query(0, mid, i))
				l = mid+1;
			else
				r = mid;
		}
		ans[i] = ans[l];
		d.unite(i, l);
	}

	cout << 0 << ' ';
	for (int i = 0; i < N; i++)
		cout << ans[i] << ' ';
	cout << endl;
}

int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	solve();
	return 0;
}

Compilation message

carnival.cpp: In function 'bool query(int, int, int)':
carnival.cpp:43:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  return res == st.size();
      |         ~~~~^~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 200 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 200 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 200 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 200 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 200 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -