Algoogle

Algorithm for Programming Contest

AOJ 2632 Dense Amidakuji

Category: AOJ Tag: implementation

Dense Amidakuji

問題概要


w(<=200000)本の縦棒からなるあみだくじがある.
縦棒の高さはh(<=200000)で,横線を高さが整数の部分の隣接する縦棒間における.
今,a≡b(mod 2)となるすべての位置(a,b)から右に横棒を置く.
ここからn(<=200000)本の横棒を指定されたように除去するとき,あみだくじの結果はどうなるか.

解法


除去前のあみだくじは規則正しく,高さが2wの周期で同じになっている.
横棒を取り除くという操作は,その両端にくる値の結果の位置を入れ替えることに相当する.
つまりどこからその値がきているかを調べ,その値を入れ替えて横棒自体にはなにもしなくてよい.
ただし,あみだくじの性質上値は上から下へ結果が伝播するので取り除く操作は上から順にやる.
あとはどこから来たかだが,このあみだくじは端から端まで階段を降りるような形なのでその逆をやればよい.
ただし端から端へは1段ずつではなく一気にいくことと,高さが2wの周期で同じなのでその分だけ調べること.

コード


(2632.cpp) download
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
#include <bits/stdc++.h>
using namespace std;

int h, w, n, seq[200010];
pair<int,int> bs[200010];

int value(int i, int j)
{
        i %= 2*w;
        while(i) {
                int tmp;
                if((i+j)%2) tmp = min(i, w-j-1);
                else tmp = -min(i,j);
                j += tmp;
                i -= abs(tmp);
                if(i) i--;
        }
        return j;
}

void solve()
{
        sort(bs, bs+n);
        for (int i = 0; i < w; i++) seq[i] = i;
        for (int i = 0; i < n; i++) {
                int p = bs[i].first, l = bs[i].second, r = l+1;
                //cerr << "(" << p << "," << l << "," << r << ") => (" << value(p,l) << "," << value(p,r) << ")" << endl;
                swap(seq[value(p,l)], seq[value(p,r)]);
        }
        int ans[200010];
        for (int i = 0; i < w; i++) ans[seq[value(h,i)]] = i+1;
        for (int i = 0; i < w; i++) printf("%d\n", ans[i]);
}

void input()
{
        scanf("%d%d%d", &h, &w, &n);
        int a, b;
        for (int i = 0; i < n; i++) {
                scanf("%d%d", &a, &b);
                bs[i] = make_pair(a-1,b-1);
        }
}

int main()
{
        input();
        solve();
        return 0;
}

Comments