백준17384 대진표

작성일 | In

문제 링크

  • http://icpc.me/

문제 출처

  • 2019 UCPC 본선 L번

시간복잡도

  • O(N)

풀이

[s, e]구간에 x명의 사람을 배치하는 경우, x가 (e-s+1)/2보다 클 때와 그렇지 않을 때를 구분하여 서로 다른 전략을 적당하게 취해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

void f(int s, int e, int x){
	if(s == e){
		if(x) cout << "#";
		else cout << ".";
		return;
	}
	int len = e - s + 1;
	if(x <= len / 2){
		int m = s + e >> 1;
		f(s, m, x); f(m+1, e, 0);
	}else{
		int m = s + e >> 1;
		int xx = 1;
		while(xx * 2 <= x - xx * 2 && xx * 2 <= e-m) xx = xx * 2;
		if(x - xx > m - s + 1) xx = x - (m - s + 1);
		f(s, m, x - xx); f(m+1, e, xx);
	}
}

int f(int n){
	int ret = 1;
	for(; ret < n; ret <<= 1);
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	f(1, f(n), n);
}