HDU 6040---Hints of sd0061(STL)

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

题意：输入n,m,A,B,C 由ABC和题中提供的函数可以得到n个数的数组a[n] ，然后输入m个数表示数组b[m]，现在对于每个b[i]输出a[]数组中的第b[i]+1小的数。题中给出b[]数组的限制bi+bj≤bk is satisfied if bi≠bj, bi<bk and bj<bk；

思路：可以发现b[]数组不是很大，对于每个b[i]找a[]数组的第b[i]+1的数时，可以使用nth(a,a+p,a+n) 这个STL函数，进行一次o(n)的排序，使得a[p]之前的数均小于a[p]，a[p]之后的数均大于a[p]，所以a[p]即为我们要的数。在对每个b[]元素操作时，可以对b[]排序,从大到小进行计算，以为之前排序的右半部分不必再进行排序，这样会减少很多计算量。

代码如下：

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

using namespace std;

const int N=1e7+;

unsigned x,y,z, A,B,C;

unsigned a[N];

struct Node

{

    int x;

    int id;

    unsigned y;

}tr[];

bool cmp(const Node s1,const Node s2)

{

    return s1.x<s2.x;

}

bool cmp2(const Node s1,const Node s2)

{

    return s1.id<s2.id;

}

unsigned rng61() {

  unsigned t;

  x ^= x << ;

  x ^= x >> ;

  x ^= x << ;

  t = x;

  x = y;

  y = z;

  z = t ^ x ^ y;

  return z;

}

int main()

{

    ///cout << "Hello world!" << endl;

    int n,m,Case=1;

    while(scanf("%d%d%u%u%u",&n,&m,&A,&B,&C)!=EOF)

    {

        x = A, y = B, z = C;

        for(int i=;i<n;i++)  a[i]=rng61();

        printf("Case #%d:",Case++);

        for(int i=;i<=m;i++) scanf("%d",&tr[i].x),tr[i].id=i;

        sort(tr+,tr+m+,cmp);

        int p=n;

        for(int i=m;i>=;i--)

        {

            int x = tr[i].x;

            nth_element(a,a+x,a+p);

            p=x;

            tr[i].y=a[x];

        }

        sort(tr+,tr+m+,cmp2);

        for(int i=;i<=m;i++) printf(" %u",tr[i].y);

        puts("");

    }

    return ;

}

秒客网

HDU 6040---Hints of sd0061(STL)

相关文章