# 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;
}