Submission #115843

#	Time	Username	Problem	Language	Result	Execution time	Memory
115843		Origims	Carnival (CEOI14_carnival)	C++14	0 / 100	40 ms	432 KiB

carnival

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define FF first
#define SS second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pie;
const int MOD = 1e9 + 7;
const int INF = 2e9;
const ll LINF = 4e18;
const ll delta = 10067;

const int N = 2e2 + 20;
vector<int> p;
int dsu[N], n, cnt = 1, ans[N];
bool mark[N][N];

int find(int v) {
	return dsu[v] < 0 ? v : dsu[v] = find(dsu[v]);
}

void merge(int v, int u) {
	if ((v = find(v)) == (u = find(u))) return ;
	if (dsu[v] > dsu[u]) swap(v, u);
	dsu[v] += dsu[u];
	dsu[u] = v;
}

int main() {
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	memset(ans, -1, sizeof ans);
	memset(dsu, -1, sizeof dsu);
	cin >> n;
	for (int i = 1; i <= n; i++)
		p.push_back(i);
	shuffle(p.begin(), p.end(), rng);
	int rem = 3499, saf = 50000;
	while (rem) {
		saf--;
		for (int i = 1; i < n; i++) {
			saf--;
			if (find(p[i - 1]) != find(p[i]) && !mark[p[i - 1]][p[i]] && rem > 0) {
				rem--;
				mark[p[i - 1]][p[i]] = mark[p[i]][p[i - 1]] = 1;
				cout << 2 << ' ' << p[i - 1] << ' ' << p[i] << endl;
				int rep;
				cin >> rep;
				if (rep == 1)
					merge(p[i], p[i - 1]);
			}
		}
		if (saf <= 0)
			break;
		shuffle(p.begin(), p.end(), rng);
	}
	cout << 0 << ' ';
	for (int i = 1; i <= n; i++) {
		if (ans[find(i)] == -1)
			ans[find(i)] = cnt++;
		cout << ans[find(i)] << ' ';
	}
	cout << endl;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20