oj.uz

답안 #335026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335026 2020-12-10T20:23:59 Z Plurm 도서관 (JOI18_library) C++11
100 / 100
 537 ms 748 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

int p[1024];
int fn(int x){
	if(p[x] == -1) return x;
	else return p[x] = fn(p[x]);
}
bool un(int x, int y){
	x = fn(x);
	y = fn(y);
	if(x == y) return false;
	p[x] = y;
	return true;
}
int queryRange(int L, int R, int N, int sp = -1){
	bitset<1024> s;
	vector<int> M(N);
	for(int i = L; i <= R; i++){
		s[fn(i)] = true;
	}
	if(sp != -1) s[fn(sp)] = true;
	for(int i = 0; i < N; i++){
		if(s[fn(i)]) M[i] = 1;
		else M[i] = 0;
	}
	return Query(M);
}
int countRange(int L, int R, int sp = -1){
	bitset<1024> s;
	for(int i = L; i <= R; i++){
		s[fn(i)] = true;
	}
	if(sp != -1) s[fn(sp)] = true;
	return s.count();
}
int LeftTurn(int L, int N){
	// L -> x duplicates
	// L -> x-1 does not duplicate
	vector<int> active;
	bitset<1024> s;
	for(int i = L; i < N; i++){
		int cur = fn(i);
		if(!s[cur]){
			active.push_back(i);
			s[cur] = true;
		}
	}
	if(queryRange(L, N-1, N, L) == countRange(L, N-1, L)) return -1;
	int lo = 0;
	int hi = active.size()-1;
	int mid;
	while(lo < hi){
		mid = (lo + hi)/2;
		if(queryRange(L, active[mid], N, L) == countRange(L, active[mid], L)) lo = mid+1;
		else hi = mid;
	}
	return active[lo];
}
int RightTurn(int R, int N){
	// x <- R duplicates
	// x+1 <- R does not duplicate
	vector<int> active;
	bitset<1024> s;
	for(int i = R; i >= 0; i--){
		int cur = fn(i);
		if(!s[cur]){
			active.push_back(i);
			s[cur] = true;
		}
	}
	reverse(active.begin(), active.end());
	if(queryRange(0, R, N, R) == countRange(0, R, R)) return -1;
	int lo = 0;
	int hi = active.size()-1;
	int mid;
	while(lo < hi){
		mid = (lo + hi + 1)/2;
		if(queryRange(active[mid], R, N, R) == countRange(active[mid], R, R)) hi = mid-1;
		else lo = mid;
	}
	return active[lo];
}
vector<int> g[1024];
void addEdge(int u, int v){
	g[u].push_back(v);
	g[v].push_back(u);
}
int findLeaf(int u, int p = -1){
	for(int v : g[u]){
		if(v == p) continue;
		return findLeaf(v, u);
	}
	return u;
}
pair<int,int> findExtremum(int u){
	if(g[u].size() > 1){
		return make_pair(findLeaf(g[u][0], u), findLeaf(g[u][1], u));
	}else if(g[u].size() == 1){
		return make_pair(u, findLeaf(g[u][0], u));
	}else{
		return make_pair(u, u);
	}
}
bool checkPair(int l, int r, int N){
	vector<int> M(N);
	fill(M.begin(), M.end(), 0);
	M[l] = M[r] = 1;
	return Query(M) == 1;
	//return g[l].size() < 2 && g[r].size() < 2;
}
void Solve(int N)
{
	memset(p, -1, sizeof(p));
	vector<int> M(N);
	for(int i = 1; i < N; i++){
		int l = LeftTurn(0, N);
		int r = RightTurn(l, N);
		int l1, l2;
		tie(l1, l2) = findExtremum(l);
		int r1, r2;
		tie(r1, r2) = findExtremum(r);
		if(checkPair(l1, r1, N)){
			l = l1;
			r = r1;
		}else if(checkPair(l1, r2, N)){
			l = l1;
			r = r2;
		}else if(checkPair(l2, r1, N)){
			l = l2;
			r = r1;
		}else if(checkPair(l2, r2, N)){
			l = l2;
			r = r2;
		}
		un(l, r);
		addEdge(l, r);
	}
	int last = -1;
	int leaf = findLeaf(0);
	vector<int> ans;
	for(int i = 0; i < N; i++){
		ans.push_back(leaf+1);
		int nxt = -1;
		for(int v: g[leaf]){
			if(v != last) nxt = v;
		}
		last = leaf;
		leaf = nxt;
	}
	Answer(ans);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 364 KB # of queries: 2812
2 Correct 49 ms 364 KB # of queries: 2807
3 Correct 52 ms 364 KB # of queries: 2978
4 Correct 54 ms 364 KB # of queries: 2971
5 Correct 45 ms 364 KB # of queries: 2948
6 Correct 55 ms 492 KB # of queries: 2918
7 Correct 54 ms 384 KB # of queries: 2950
8 Correct 36 ms 492 KB # of queries: 2805
9 Correct 53 ms 364 KB # of queries: 2961
10 Correct 26 ms 364 KB # of queries: 1749
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 1 ms 384 KB # of queries: 5
13 Correct 1 ms 364 KB # of queries: 12
14 Correct 1 ms 364 KB # of queries: 20
15 Correct 2 ms 364 KB # of queries: 117
16 Correct 5 ms 364 KB # of queries: 251

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 364 KB # of queries: 2812
2 Correct 49 ms 364 KB # of queries: 2807
3 Correct 52 ms 364 KB # of queries: 2978
4 Correct 54 ms 364 KB # of queries: 2971
5 Correct 45 ms 364 KB # of queries: 2948
6 Correct 55 ms 492 KB # of queries: 2918
7 Correct 54 ms 384 KB # of queries: 2950
8 Correct 36 ms 492 KB # of queries: 2805
9 Correct 53 ms 364 KB # of queries: 2961
10 Correct 26 ms 364 KB # of queries: 1749
11 Correct 1 ms 364 KB # of queries: 0
12 Correct 1 ms 384 KB # of queries: 5
13 Correct 1 ms 364 KB # of queries: 12
14 Correct 1 ms 364 KB # of queries: 20
15 Correct 2 ms 364 KB # of queries: 117
16 Correct 5 ms 364 KB # of queries: 251
17 Correct 513 ms 684 KB # of queries: 19260
18 Correct 494 ms 496 KB # of queries: 18977
19 Correct 515 ms 748 KB # of queries: 19264
20 Correct 459 ms 620 KB # of queries: 17994
21 Correct 437 ms 492 KB # of queries: 16986
22 Correct 522 ms 504 KB # of queries: 19329
23 Correct 537 ms 492 KB # of queries: 19264
24 Correct 205 ms 364 KB # of queries: 8911
25 Correct 483 ms 492 KB # of queries: 18870
26 Correct 446 ms 556 KB # of queries: 17603
27 Correct 165 ms 492 KB # of queries: 8870
28 Correct 355 ms 424 KB # of queries: 12973
29 Correct 359 ms 560 KB # of queries: 12959
30 Correct 329 ms 620 KB # of queries: 12973