Hints of sd0061

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

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

//题意: n,m,a,b,c abc为3个参数，用这些参数生成n个数，然后，求排好序后的 n 个数中，m 次查询，第 i 的数的值

//题解：这种数据下 10e7 ，不能直接用快排，就算快排，还是会超时，但是要利用快排的思想。因为 m 比较小，可以这样，每次快排结束后，前部分一定比分界值小或等，后半部分一定大或等，要查询第 k 大的数时，如果 k 在分界位置左边，就只排左边，在右就只排右，这样，每阶段快排省去一半区间，就行了，还wa了一发，很蛋疼，因为生成数据那部分不能直接用LL，只能用题目给的unsigned ，卡数据，很难玩那！

但是还是差点超时 2300ms ，评测机卡还有可能TLE，我擦，让我再想想怎么优化

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 #define LL long long

 #define MXN 10000005

 #define MXM 105

 int num[MXM];

 LL prt[MXM];

 LL data[MXN];

 bool vis[MXN];

 int n,m;

 unsigned x,y,z;

 unsigned rng61(){

   LL t;

   x ^= x << ;

   x ^= x >> ;

   x ^= x << ;

   t = x;

   x = y;

   y = z;

   z = t ^ x ^ y;

   return z;

 }

 void qk_sort(int l,int r,int k)

 {

     if (l>=r) return;

     int a=l, b=r;

     while (a<b)

     {

         while (a<b&&data[b]>=data[l]) b--;

         while (a<b&&data[a]<=data[l]) a++;

         swap(data[a],data[b]);

     }

     swap(data[l],data[a]);

     vis[a]=;

     if (k==a) return;

     if (k<a) qk_sort(l,a-,k);

     if (k>a) qk_sort(a+,r,k);

 }

 int main()

 {

     int cnt=;

     while (scanf("%d%d%u%u%u",&n,&m,&x,&y,&z)!=EOF)

     {

         for (int i=;i<m;i++)

             scanf("%d",&num[i]);

         for (int i=;i<n;i++)

             data[i]=(LL)rng61();

         memset(vis,,sizeof(vis));

         for (int i=;i<m;i++)

         {

             int l =num[i],r=num[i];

             while (l>=&&vis[l]==) l--;

             l++;

             while (r<n&&vis[r]==) r++;

             r--;

             qk_sort(l,r,num[i]);

             prt[i] = data[num[i]];

         }

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

         for (int i=;i<m;i++)

             printf(" %lld",prt[i]);

         printf("\n");

     }

     return ;

 }

STL 里面的 nth_element(arr,arr+x,arr+n);

可以将x在[0,n]范围内，将第x小的数字移动到arr[x]上，其余比arr[x]大的，在x后面，比arr[x]小的，在x前面。

1684 ms

STL 用得好省事多啊

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define MXN 10000005

 #define MXM 105

 struct Node

 {

     int w;

     int p;

     bool operator <(const Node b) const

     {

         return w<b.w;

     }

 }num[MXM];

 LL prt[MXM];

 LL data[MXN];

 bool vis[MXN];

 int n,m;

 unsigned x,y,z;

 unsigned rng61(){

   LL t;

   x ^= x << ;

   x ^= x >> ;

   x ^= x << ;

   t = x;

   x = y;

   y = z;

   z = t ^ x ^ y;

   return z;

 }

 int main()

 {

     int cnt=;

     while (scanf("%d%d%u%u%u",&n,&m,&x,&y,&z)!=EOF)

     {

         for (int i=;i<m;i++)

         {

             scanf("%d",&num[i].w);

             num[i].p=i;

         }

         sort(num,num+m);

         for (int i=;i<n;i++)

             data[i]=(LL)rng61();

         memset(vis,,sizeof(vis));

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

         {

             if (i==m-)

                 nth_element(data,data+num[i].w,data+n);

             else

                 nth_element(data,data+num[i].w,data+num[i+].w);

             prt[num[i].p] = data[num[i].w];

         }

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

         for (int i=;i<m;i++)

             printf(" %lld",prt[i]);

         printf("\n");

     }

     return ;

 }

巴特西

Hints of sd0061(快排思想)

Hints of sd0061

最新文章

热门文章