oj.uz

답안 #260370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260370 2020-08-10T07:27:57 Z 임성재(#5050) 도서관 (JOI18_library) C++17
100 / 100
 370 ms 764 KB 
#include "library.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair

static int p[1010];
static vector<int> M;
static vector<int> v[1010];
int n;

static void cl() {
	for(int i=0; i<n; i++) M[i] = 0;
}

static int Find(int a) {
	return p[a] = p[a] == a ? a : Find(p[a]);
}

static void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	p[b] = a;

	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}

	reverse(all(v[b]));
	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}

	reverse(all(v[a]));
	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}

	reverse(all(v[b]));
	cl();
	M[v[a].back() - 1] = M[v[b].front() - 1] = 1;

	if(Query(M) == 1) {
		for(auto i : v[b]) {
			v[a].eb(i);
		}
		v[b].clear();
		return;
	}
}

void f(int s, int e, int x, int k) {
	if(s == e) {
		Union(s, x);

		return;
	}

	int m = (s + e) / 2;

	cl();

	M[x-1] = 1;

	int t = 1;

	for(int i=s; i<=m; i++) {
		if(Find(i) != i) continue;

		t++;

		for(auto j : v[i]) {
			M[j-1] = 1;
		}
	}

	t -= Query(M);

	if(t) f(s, m, x, t);
	if(k - t) f(m+1, e, x, k-t);
}

void Solve(int N)
{
	n = N;
	for(int i=1; i<=N; i++) 
		p[i] = i, v[i].eb(i);

	M.resize(N, 0);

	int sz = 0;
	for(int i=1; i<=N; i++) {
		cl();

		for(int j=1; j<=i; j++) M[j-1] = 1;

		int k = Query(M);

		if(k < sz + 1) f(1, i-1, i, sz + 1 - k);

		sz = k;
	}

	for(int i=1; i<=N; i++) {
		if(Find(i) == i) {
			Answer(v[i]);
			return;
		}
	}
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 384 KB # of queries: 1747
2 Correct 37 ms 384 KB # of queries: 1762
3 Correct 30 ms 384 KB # of queries: 1809
4 Correct 35 ms 512 KB # of queries: 1793
5 Correct 26 ms 436 KB # of queries: 1827
6 Correct 34 ms 504 KB # of queries: 1842
7 Correct 38 ms 384 KB # of queries: 1816
8 Correct 28 ms 384 KB # of queries: 1739
9 Correct 30 ms 384 KB # of queries: 1847
10 Correct 17 ms 400 KB # of queries: 1073
11 Correct 0 ms 384 KB # of queries: 1
12 Correct 1 ms 384 KB # of queries: 3
13 Correct 1 ms 384 KB # of queries: 8
14 Correct 1 ms 384 KB # of queries: 13
15 Correct 1 ms 384 KB # of queries: 78
16 Correct 3 ms 384 KB # of queries: 160

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 384 KB # of queries: 1747
2 Correct 37 ms 384 KB # of queries: 1762
3 Correct 30 ms 384 KB # of queries: 1809
4 Correct 35 ms 512 KB # of queries: 1793
5 Correct 26 ms 436 KB # of queries: 1827
6 Correct 34 ms 504 KB # of queries: 1842
7 Correct 38 ms 384 KB # of queries: 1816
8 Correct 28 ms 384 KB # of queries: 1739
9 Correct 30 ms 384 KB # of queries: 1847
10 Correct 17 ms 400 KB # of queries: 1073
11 Correct 0 ms 384 KB # of queries: 1
12 Correct 1 ms 384 KB # of queries: 3
13 Correct 1 ms 384 KB # of queries: 8
14 Correct 1 ms 384 KB # of queries: 13
15 Correct 1 ms 384 KB # of queries: 78
16 Correct 3 ms 384 KB # of queries: 160
17 Correct 329 ms 564 KB # of queries: 11487
18 Correct 370 ms 504 KB # of queries: 11396
19 Correct 363 ms 760 KB # of queries: 11440
20 Correct 340 ms 764 KB # of queries: 10733
21 Correct 327 ms 384 KB # of queries: 10140
22 Correct 306 ms 508 KB # of queries: 11473
23 Correct 320 ms 568 KB # of queries: 11455
24 Correct 102 ms 508 KB # of queries: 5336
25 Correct 297 ms 384 KB # of queries: 11233
26 Correct 277 ms 632 KB # of queries: 10519
27 Correct 107 ms 424 KB # of queries: 5338
28 Correct 311 ms 508 KB # of queries: 10966
29 Correct 319 ms 384 KB # of queries: 10954
30 Correct 306 ms 432 KB # of queries: 10966