https://codeforces.com/contest/1647

E. Madoka and the Sixth-graders

 

题意：房间里有 nn 个座位，第 ii 个座位上的人的编号为 bi∈{1,2,⋯ ,n}b_i\in\{1,2,\cdots,n\}，每一轮座位 ii 上的人移动到座位 pi∈{1,2,⋯ ,n}p_i\in \{1, 2,\cdots,n\}，若多个人移到同一个座位，则编号最小的人留下，其他人永远离开游戏。房间外有无限多的人，编号为 n+1,n+2,⋯n+1,n+2,\cdots，每一轮移动后必定空出座位，房间外的人按编号顺序坐到空座位上。经过若干轮后，最终座位 ii 上的人的编号为 aia_i。给定 ai,pia_i,p_i，问初始排列 bib_i，保证有解，输出字典序最小的解。

倍增

把 pp 建成图，入度为 00 的就是空座位，且每轮都一样。通过空座位上的人的编号可以知道游戏进行了几轮，记为 CC。

倍增得到 CC 轮后初始每个座位上的人会移动到哪个座位（如果中间没死的话）。

假设 {x1,x2,x3}\{x_1, x_2, x_3\} 最终能够移动到座位 ii，最终活下来的 a[i]a[i]，一定是 {b[x1],b[x2],b[x3]}\{b[x_1],b[x_2],b[x_3]\} 中编号最小的人，由于题目要求字典序最小的解，所以要把这个人放在第 min⁡{x1,x2,x3}\min\{x_1, x_2, x_3\} 个座位上，其他人的编号无所谓，但是一定要小于 a[i]a[i]。

把入度不为 00 的座位分配好之后，其他人从小到大分配，但是一定要保证被分配到坐到第 ii 个座位上的人的编号小于第 ii 个座位上的人最终移动到的座位上的人的编号。

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
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
const int N = 2e5 + 10;
typedef pair<int, int> pii;

int n;
int p[N], a[N], b[N], fa[N][40], d[N], dst[N];
set<int>st;
priority_queue<int, vector<int>, greater<int> >q[N];


int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)scanf("%d", &p[i]), d[p[i]]++;
    for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++)fa[i][0] = p[i];
    for(int i = 1; i < 40; i++){
        for(int j = 1; j <= n; j++){
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
        }
    }
    int cnt = 0, fs = 0;
    for(int i = 1; i <= n; i++){
        if(d[i] == 0)cnt++;
        if(fs == 0 && d[i] == 0)fs = i;
    }
    int c;
    if(a[fs] <= n)c = 0;
    else c = (a[fs] - n - 1) / cnt + 1;
    for(int i = 1; i <= n; i++){
        int tmp = c, u = i;
        for(int j = 0; j < 40; j++){
            if(tmp & 1)u = fa[u][j];
            tmp >>= 1;
        }
        dst[i] = u;
        q[u].push(i);
    }
    for(int i = 1; i <= n; i++)st.insert(i);
    for(int i = 1; i <= n; i++){
        if(!q[i].empty()){
            b[q[i].top()] = a[i];
            st.erase(a[i]);
        }
    }
    for(int i = 1; i <= n; i++){
        if(!b[i]){
            auto pp = st.upper_bound(a[dst[i]]);
            b[i] = *pp;
            st.erase(pp);
        }
    }
    for(int i = 1; i <= n; i++)printf("%d%c", b[i], " \n"[i == n]);
    return 0;
}