444B

Description

There are two sequences called $a$ and $b$ of length $n$.

$a$ is a permutation of 1~$n$.

$b$ have $d$ ones and $n-d$ zeros.

$c_i=max(a_{i-j}b_j)$,$(0\leq j\leq i)$.

Tutorial

Set an value to $s$. ($1 \leq s \leq n$) For each $c_i$, we try the answer $x$ from $n$ to $s$. We can know whether $c_i = x$ in $O(1)$ with a preprocessing of recording the position of each number in $a$.

If the answer is not found with the operations above, we calculated with brute force. But we first record the position of each "1" in $b$, and we only check the "1"s to accelerate the brute force process.

Solution

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define MAX_N 100005
#define D(x) 

int a[MAX_N], b[MAX_N];
int n, d;
long long x;
int one_num, one_pos[MAX_N];
int pos_a[MAX_N];
int ans[MAX_N];

void output(int ans[])
{
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", ans[i]);
    }
}

int getNextX() {
    x = (x * 37 + 10007) % 1000000007;
    return x;
}

void initAB() {
    int i;
    for(i = 0; i < n; i = i + 1){
        a[i] = i + 1;
    }
    for(i = 0; i < n; i = i + 1){
        swap(a[i], a[getNextX() % (i + 1)]);
    }
    for(i = 0; i < n; i = i + 1){
        if (i < d)
            b[i] = 1;
        else
            b[i] = 0;
    }
    for(i = 0; i < n; i = i + 1){
        int y;
        swap(b[i], b[y = getNextX() % (i + 1)]);
        D(printf("%d%d\n", i, y));
        D(output(b));
        D(puts(""));
    }
}

void work()
{
    int s = 30;
    for (int i = 0; i < n; i++)
    {
        if (b[i] == 1)
        {
            one_pos[one_num++] = i;
        }
    }

    for (int i = 0; i < n; i++)
    {
        a[i]--;
        pos_a[a[i]] = i;
    }

    memset(ans, 0, sizeof(ans));
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = n - 1; j >= n - s && j >= 0; j--)
        {
            if (pos_a[j] <= i && b[i - pos_a[j]] == 1)
            {
                ans[i] = j + 1;
                break;
            }
        }

        if (ans[i] != 0)
        {
            continue;
        }

        for (int j = 0; j < one_num; j++)
        {
            if (i - one_pos[j] < 0)
            {
                break;
            }
            ans[i] = max(ans[i], a[i - one_pos[j]] + 1);
        }
    }
}
void input()
{
    int xx;
    scanf("%d%d%d", &n, &d, &xx);
    x = xx;
}

int main()
{
    input();
    initAB();
    work();
    output(ans);
    return 0;
}