首页 > 代码库 > HDU 6040 stl

HDU 6040 stl

2024-11-19 19:52:39   203人阅读

Hints of sd0061

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


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 10 1 22 2 2 2 21 1
 

 

Sample Output
Case #1: 1 1 202755Case #2: 405510 405510
 

 

Source
2017 Multi-University Training Contest - Team 1
 
 1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <bits/stdc++.h> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <iostream> 6 #include <cstdlib> 7 #include <cstring> 8 #include <algorithm> 9 #include <cmath>10 #include <cctype>11 #include <map>12 #include <set>13 #include <queue>14 #include <bitset>15 #include <string>16 #include <complex>17 #define LL long long18 #define mod 100000000719 using namespace std;20 int n,m;21 unsigned x,y,z,t,ans[10000007];22 unsigned rng61(){23     x^=x<<16;24     x^=x>>5;25     x^=x<<1;26     t=x;27     x=y;28     y=z;29     z=t^x^y;30     return z;31 }32 unsigned  aa[10000007];33 struct node34 {35     int xx;36     int pos;37     friend bool operator < (node aaa,node bbb)38     {39         return aaa.xx < bbb.xx;40     }41 }bb[105];42 int main()43 {44     int t=0;45     while(scanf("%d %d %u %u %u",&n,&m,&x,&y,&z)!=EOF){46         for(int i=1; i<=m; i++){47             scanf("%d",&bb[i].xx);48             bb[i].pos=i;49             }50         for(int i=0; i<n; i++)51             aa[i]=rng61();52         sort(bb+1,bb+1+m);53         bb[m+1].xx=n;54         for(int i=m;i>=1;i--){55             nth_element(aa,aa+bb[i].xx,aa+bb[i+1].xx);56             ans[bb[i].pos]=aa[bb[i].xx];57         }58         printf("Case #%d:",++t);59         for(int i=1;i<=m;i++)60             printf(" %u",ans[i]);61         printf("\n");62     }63     return 0;64 }

 

HDU 6040 stl


联系
我们