Algoogle

Algorithm for Programming Contest

Codeforces 444B DZY Loves FFT

Category: Codeforces Tag: math

DZY Loves FFT

問題概要


a, b(aは1~nの順列, bはd個の1とn-d個の0の順列)があるとき

で表されるcの列を求めよ.

解法


dが小さいとき, 1となるbの位置を列挙しておけばそれぞれの位置に対してaの値を見ればcをO(nd)で求められる.
dが大きいとき, 各位置で1になる確率が高くなるのでaの値が大きいものから最大になる場所を埋めていけば良い.
既に埋まっている場所を候補から除外しておけば各位置で1になる確率が高いことからどんどん候補が減っていくはず.
bは擬似乱数によって生成されるので悪意ある入力は考慮しなくて良い.
今回は候補をpriority_queueに入れて, 現在の値が出現しなくなる位置まで取り出してその位置で最大値になれるか確認するのと, なれない場合ははpriority_queueに戻すという操作で実装した.

コード


(444B.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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
const int D = 1000;

int n, d, a[100010], b[100010], c[100010], p[100010];
long long x;

inline long long getx()
{
        return x = (x*37+10007)%1000000007;
}

void gen()
{
        for (int i = 0; i < n; i++) {
                a[i] = i+1;
                b[i] = (i < d);
        }
        for (int i = 0; i < n; i++) {
                swap(a[i], a[getx()%(i+1)]);
        }
        for (int i = 0; i < n; i++) {
                p[a[i]] = i;
                swap(b[i], b[getx()%(i+1)]);
        }
}

void solve_s()
{
        vector<int> ok;
        for (int i = 0; i < n; i++)
                if(b[i]) ok.push_back(i);
        for (int i = 0; i < n; i++) {
                for(auto &e: ok) {
                        if(e > i) break;
                        c[i] = max(c[i], a[i-e]);
                }
        }
}

void solve_l()
{
        priority_queue<int> q;
        for (int i = 0; i < n; i++) q.push(i);
        for (int i = n; i > 0; i--) {
                vector<int> next;
                while (!q.empty()) {
                        int v = q.top();
                        if(v < p[i]) break;
                        q.pop();
                        if(b[v-p[i]]) c[v] = i;
                        else next.push_back(v);
                }
                for(auto &e: next) q.push(e);
        }
}

int solve()
{
        gen();
        if(d <= D) solve_s();
        else solve_l();
        for (int i = 0; i < n; i++) printf("%d\n", c[i]);
        return 0;
}

void input()
{
        cin >> n >> d >> x;
}

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

Comments