首页 > > 程序设计 > C/C++ >

HDU 6040---Hints of sd0061(STL)

2018-06-17 22:10:38来源：未知阅读 ()

题目链接

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

Input

There are multiple test cases (about

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 #" in one line (without quotes), where

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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e7+5;
unsigned x,y,z, A,B,C;
unsigned a[N];
struct Node
{
    int x;
    int id;
    unsigned y;
}tr[105];
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 << 16;
  x ^= x >> 5;
  x ^= x << 1;
  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=0;i<n;i++)  a[i]=rng61();
        printf("Case #%d:",Case++);
        for(int i=1;i<=m;i++) scanf("%d",&tr[i].x),tr[i].id=i;
        sort(tr+1,tr+m+1,cmp);

        int p=n;
        for(int i=m;i>=1;i--)
        {
            int x = tr[i].x;
            nth_element(a,a+x,a+p);
            p=x;
            tr[i].y=a[x];
        }
        sort(tr+1,tr+m+1,cmp2);
        for(int i=1;i<=m;i++) printf(" %u",tr[i].y);
        puts("");
    }
    return 0;
}