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