|
|
back to boardCommon Boardmeat store A brand new equipment has been installed in meat store recently - the electronic seller. Now the customer can simply come and press the button, and the seller will select the meat piece automatically. The pieces are stored in a special container inside the seller. Different pieces have different weights (all weights are distinct). There are N pieces of meat in the container. The seller works the following way. There is a special register X in seller circuit, with initial value set to 0. In order to satisfy the customer the seller does the following: All pieces are numbered from 0 to N-1 in order of weight increase. The piece with number equal to register X value is selected. The seller retrieves the selected piece from the container and hands it to the customer. A request for a new piece is sent to a special warehouse. There are M pieces of meat at the warehouse initially (all weights are distinct). When a request comes, a piece with maximal weight is selected and sent to the container. Thus, the total number of pieces in container remains the same, and the warehouse gets empty after serving M requests. A new value XAB is written into register X which is calculated like this: XAB = (X · A + B) mod N Suppose, that the customer requires K pieces. You must write a program that will calculate the sequence of pieces given out by the seller. Input The first line contains 5 integer numbers N, M, A, B, K (2 ≤ N, M ≤ 2^16; 1 ≤ K ≤ M; 0 < A < N; 0 ≤ B < N). The second line contains N integers - weights of pieces in the container. The third line contains M integers - weights of pieces in the warehouse. All weights are distinct. All weights are between 1 and 231-1 inclusively. Output Output K numbers separated by spaces - weights of pieces in order of giving out. Input 1 Output 1 3 2 1 1 2 5 1 3 4 2 1 4 Input 2 Output 2 3 3 2 1 3 5 2 3 1 4 6 2 5 3 //Already I compiled programm but n=65536 time limited This is meat store`s code in c++ #include <iostream.h> #include <conio.h> #include <algorithm> using namespace std; void qs(int* y, int first, int last) { int i = first, j = last, x = y[(first + last) / 2],xx; do { while (y[i] < x) i++; while (y[j] > x) j--; if(i <= j) { if (y[i] > y[j]) {xx=y[i];y[i]=y[j];y[j]=xx;} i++; j--; } } while (i <= j); if (i < last) qs(y, i, last); if (first < j) qs(y, first, j); } int main() { int n,m,k,a,b; cin>>n>>m>>a>>b>>k; int *y,*z,xx; y=new int[n+1]; z=new int[m+1]; for(int i=0;i<n;i++) cin>>y[i]; for(int j=0;j<m;j++) cin>>z[j]; qs(y,0,n-1); qs(z,0,m-1); int x=0; cout<<y[0]<<" "; int pp; for(int t=1;t<k;t++) { pp=z[m-t]; y[x]=y[n/2]; y[n/2]=pp; qs(y,0,n-1); x=(x*a+b) % n; cout<<y[x]<<" "; } //getch(); // return 0; } Edited by author 03.11.2014 22:16 Edited by author 03.11.2014 22:21 |
|
|