444B


  Posted on 07 Dec 2014
random algorithm implementation

Description


There are two sequences called and of length .

is a permutation of 1~.

have ones and zeros.

,.

Tutorial


Set an value to . () For each , we try the answer from to . We can know whether in with a preprocessing of recording the position of each number in .

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