oj.uz

답안 #115843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115843 2019-06-09T10:00:59 Z Origims 사육제 (CEOI14_carnival) C++14
0 / 100
 40 ms 432 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 384 KB Integer 12 violates the range [1, 11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 256 KB Output is correct
2 Incorrect 33 ms 256 KB Integer 29 violates the range [1, 28]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 20 ms 432 KB Output is correct
3 Incorrect 13 ms 308 KB Integer 59 violates the range [1, 58]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 384 KB Output is correct
2 Correct 32 ms 384 KB Output is correct
3 Incorrect 40 ms 384 KB Integer 121 violates the range [1, 120]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 364 KB Output is correct
2 Incorrect 25 ms 256 KB Integer 18 violates the range [1, 17]
3 Halted 0 ms 0 KB -