2017 Multi-University Training Contest - Team 1 ：Hints of sd0061（hdu 6040）

Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1540    Accepted Submission(s): 453

Problem Description sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with  m  coming contests.  sd0061 has left a set of hints for them.

There are  n  noobs in the team, the  i -th of which has a rating  ai .  sd0061 prepares one hint for each contest. The hint for the  j -th contest is a number  bj , which means that the noob with the  (bj+1) -th lowest rating is ordained by  sd0061 for the  j -th contest.

The coach asks  constroy to make a list of contestants.  constroy looks into these hints and finds out:  bi+bj≤bk  is satisfied if  bi≠bj,   bi<bk  and  bj<bk .

Now, you are in charge of making the list for  constroy.  

Input There are multiple test cases (about  10 ).

For each test case:

The first line contains five integers  n,m,A,B,C .  (1≤n≤107,1≤m≤100)

The second line contains  m  integers, the  i -th of which is the number  bi  of the  i -th hint.  (0≤bi<n)

The  n  noobs' ratings are obtained by calling following function  n  times, the  i -th result of which is  ai .

unsigned x = A, y = B, z = C;
unsigned rng61() {
  unsigned t;
  x ^= x << 16;
  x ^= x >> 5;
  x ^= x << 1;
  t = x;
  x = y;
  y = z;
  z = t ^ x ^ y;
  return z;
}      

Output For each test case, output " Case # x :  y1   y2   ⋯   ym " in one line (without quotes), where  x  indicates the case number starting from  1  and  yi   (1≤i≤m)  denotes the rating of noob for the  i -th contest of corresponding case.  

Sample Input

3 3 1 1 1
0 1 2
2 2 2 2 2
1 1
        

Sample Output

Case #1: 1 1 202755
Case #2: 405510 405510
        

  ，

Source 2017 Multi-University Training Contest - Team 1

  //题意：输入n,m,A,B,C，n代表要循环题目给的函数n次，每次函数结束的值都储存在Y[]（自己定义的一个数组），m表示下面那排有m个数，A,B,C分别为题目给的函数里x,y,z的初值。第二排m个数表示输出Y[]中第那个数大的值是多少。

//思路：这题要卡时间，排序不能用sort，会TLE，要用nth_element(start,start+n,end)这个函数，这个函数在c++STL库中，包含于<algorithm>，作用是把一个数组里第n大的元素放在第n个位置，时间复杂度O(nlogn)，和快排（sort）是一样的，但注意，不用把整个数组都排序完，具体怎么用自行百度。

还有一点是你输入的m个要查找的位置要先从大到小排序（用sort ，因为m非常小），尽量人为降低nth_element()的复杂度，不然会TLE，但注意输出的时候要按它m个数输入的顺序！

还有就是unsigned类型的输入是%u 。

//多校，被高中生血虐的辛酸史[捂脸]...

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1e7 + 100;
const int MAX = 100 + 10;

typedef struct {
	unsigned id;
	unsigned val;
}rrank;

unsigned x, A, y, B, z, C;
unsigned Y[N];
rrank Rank[MAX];
unsigned ans[MAX];

//这里从小到大排序了
//是因为下面的循环我是从m-1 -> 0
//相当于还是从大到小排序
bool cmp(rrank p1, rrank p2)
{
	return p1.val < p2.val;
}

unsigned rng61() {
	unsigned t;
	x ^= x << 16;
	x ^= x >> 5;
	x ^= x << 1;
	t = x;
	x = y;
	y = z;
	z = t ^ x ^ y;
	return z;
}

int main()
{
	int Case = 1;
	int n, m;
	while (scanf("%u%u%u%u%u", &n, &m, &A, &B, &C) != EOF)
	{
		x = A;
		y = B;
		z = C;
		for (int i = 0; i < m; i++)
		{
			scanf("%u", &Rank[i].val);
			Rank[i].id = i;
		}

		sort(Rank, Rank + m, cmp);
		Rank[m].val = n;
		Rank[m].id = m;
		printf("Case #%d: ", Case++);

		for (int i = 0; i < n; i++)
		{
			Y[i] = rng61();
		}

		for (int i = m - 1; i >= 0; i--)
		{
			if (Rank[i].val == Rank[i + 1].val)
				ans[Rank[i].id] = ans[Rank[i + 1].id];
			else
			{
				nth_element(Y, Y + Rank[i].val, Y + Rank[i + 1].val);
				ans[Rank[i].id] = Y[Rank[i].val];
			}
		}

		for (int i = 0; i < m - 1; i++)
		{
			printf("%u ", ans[i]);
		}
		printf("%u\n", ans[m - 1]);

	}
	return 0;
}