N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다.


합을 저장하는 세그먼트트리를 구현한 후   합을 출력하는 squery 와  해당번쨰를 가리키는 값을 출력하는 query 를 구현한다.


환형임을 생각해야하므로  %modi  를 해주며 제거할 때 마다 인원수가 감소하므로 modi-- 를 해준다.


따라서 해당 위치를 제거해가며  res 배열에 답을 담아 출력한다.



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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
int n, m;
const int MAX_N = 100020;
int seg[MAX_N * 4];
 
int update(int pos, int val, int node, int x, int y) {
    if (pos < x || y < pos)    return seg[node];
    if (x == y) return seg[node] = val;
    int mid = (x + y) >> 1;
    update(pos, val, node*2, x, mid);
    update(pos, val, node * 2+1, mid + 1, y);
    seg[node] = seg[node * 2+ seg[node * 2 + 1];
}
 
int query(int val, int node, int x, int y) {
    if (x == y)    return x;
    int mid = (x + y) >> 1;
    if (val <= seg[node * 2])
        return query(val, node * 2, x, mid);
    else
        return query(val - seg[node*2], node*2+1, mid + 1, y);
}
int squery(int lo, int hi, int node, int x, int y) {
    if (hi < x || y < lo)    return 0;
    if (lo <= x && y <= hi)    return seg[node];
    int mid = (x + y) >> 1;
    return squery(lo, hi, node * 2, x, mid) + squery(lo, hi, node * 2 + 1, mid + 1, y);
}
vector<int> res;
int main() {
    freopen("input.txt""r", stdin);
    scanf("%d %d"&n, &m);
    res.push_back(m);
    int modi = n-1;
    for (int i = 1; i <= n; i++) {
        update(i, 111, n);
    }
    update(res.back(), 011, n);
    for (int i = 0; i < n-1; i++) {
        int x = (squery(1,res.back(),1,1,n) + m) % modi;
        if (!x) x = modi;
        res.push_back(query(x, 11, n));
        update(res.back(), 011, n);
        modi--;
    }
    printf("<");
    for (int i = 0; i < n; i++)
    {
        
        if (i == n - 1)
            printf("%d>\n",res[i]);
        else
        printf("%d, ", res[i]);
    }
    
 
}
 
cs


'알고리즘' 카테고리의 다른 글

codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26
acm-cicpc 수학정복  (2) 2017.09.15
[BOJ1168] 조세퍼스 문제2  (0) 2017.01.22
[BOJ5012} 불만정렬  (0) 2017.01.22
[BOJ9426] 중앙값 측정  (0) 2017.01.19

+ Recent posts