hdu 6040 Hints of sd0061(stl: nth_element(arr,arr+k,arr+n))

Hints of sd0061

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

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

Recommend

liuyiding   |   We have carefully selected several similar problems for you:  6055 6054 6053 6052 6051 

 

 

题意：给你一个长度为n的序列，序列由题面给的函数生成。然后m次询问，询问这个序列上第bi小的数。

解题思路：新学习了一个STL，C++中的nth_element(arr,arr+k,arr+n)，将长度为n的数组arr进行划分，第k-1位置上就是第k大的数（下标从0开始算），这个函数近似线性，在找到第k大的时候，前k-1个数均是小于arr[k]的，因为输入保证任意两个小的之和小于第三个，所以查询数列的间隔一定大于等于斐波那契，所以从大到小查询的话，每次至少能去掉一半的区间，根据这个可以减少搜索量

hdu上要用G++交,C++超时

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

unsigned a[10000005];
struct node
{
    int k,id;
}b[105];
int n,m;
unsigned x, y, z;

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;
}
bool cmp(node a,node b)
{
    return a.k>b.k;
}
bool cmp2(node a,node b)
{
    return a.id<b.id;
}
int main()
{
    int cas=0;
    while(~scanf("%d%d%u%u%u",&n,&m,&x,&y,&z))
    {
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&b[i].k);
            b[i].id=i;
        }
        for(int i=0;i<n;i++) a[i]=rng61();

        sort(b+1,b+1+m,cmp);
        b[0].k=n;
        for(int i=1;i<=m;i++)
        nth_element(a,a+b[i].k,a+b[i-1].k);
        sort(b+1,b+1+m,cmp2);

        printf("Case #%d:",++cas);
        for(int i=1;i<=m;i++)
         printf(" %u",a[b[i].k]);
        printf("
");
    }
    return 0;
}