pku2886.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 86 行

/*
我出的题目
这个程序可是标程哦！
*/
#include <stdio.h>
#define size 510000

typedef struct Node
{
	int s, e;
	int cnt;
} Node;

Node stree[size * 3];
char Name[size][11];
int A[size];
int N, K;
const int PV[40] = {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320, 221760, 277200, 332640, 498960, 554400, 665280};
const int Nu[40] = {1, 2, 3, 4, 6, 8, 9, 10, 12, 16, 18, 20, 24, 30, 32, 36, 40, 48, 60, 64, 72, 80, 84, 90, 96, 100, 108, 120, 128, 144, 160, 168, 180, 192, 200, 216, 224};
void CreateTree(int s, int e, int p)
{
	stree[p].s = s;
	stree[p].e = e;
	stree[p].cnt = e - s;
	if (e - s == 1)
		return;
	CreateTree(s, (s + e + 1) / 2, p * 2 + 1);
	CreateTree((s + e + 1) / 2, e, p * 2 + 2);
}

int Find(int l, int p)
{
	stree[p].cnt--;
	if (stree[p].e - stree[p].s == 1)
	{
		return stree[p].s;
	}
	if (l < stree[p * 2 + 1].cnt)
	{
		return Find(l, p * 2 + 1);
	}
	else
	{
		return Find(l - stree[p * 2 + 1].cnt, p * 2 + 2);
	}
}

void Solve()
{
	int P, i, L, ans, num;
	CreateTree(0, N, 0);
	i = 0;
	while (PV[i + 1] <= N)
		i++;
	P = PV[i];
	num = Nu[i];
	for (i = 0; i < N; i++)
	{
		scanf("%s %d", Name[i], &A[i]);
	}
	K--;
	L = N - 1;
	ans = K;
	for (i = 0; i < P; i++)
	{
		ans = Find(K, 0);
		if (L == 0)
			break;
		if (A[ans] > 0)
			K = (K + A[ans] - 1) % L;
		else
			K = ((K + A[ans]) % L + L) % L;
		L--;
	}
	printf("%s %d\n", Name[ans], num);
}

int main()
{
	while (EOF != scanf("%d%d", &N, &K))
		Solve();
	return 0;
}