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.
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.
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+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; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
