fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6.  
  7. // hàm tìm  vị trí của số x đầu tiên (vì có thể có nhiều hơn 1 số x trong mảng này) trong một mảng được sắp xếp từ bé đến lớn
  8. int binarySearch(int tmp[], int l, int r, int x){
  9.     if(r>=l){
  10.         int mid =l+(r-l)/2;
  11.         // vd tìm vị trí của số 2 trong mảng là 1 1 2 2 3 5 6 8 8; 
  12.         // thì mid = 4, tmp[mid] = 2 nhung mid chưa phải là vị trí cần tìm, mà vị trí cần tìm phỉa là mid-1
  13.         // do đó đk để return mid thì a[mid-1] < x;
  14.         if((mid == 0 || tmp[mid-1] < x) && tmp[mid] == x) return mid;
  15.         if(x < tmp[mid]) return binarySearch(tmp, l, mid-1, x);
  16.         return binarySearch(tmp, mid+1, r, x);
  17.     }
  18.     return -1;
  19. }
  20.  
  21. void sortAccording(int A[], int B[], int n, int m){
  22.     int temp[n], visited[n];
  23.  
  24.     // mảng temp là mảng chứa những phần tử của mảng A nhưng đã được sắp xếp
  25.     // mảng visited để đánh dấu phần tử đã được thăm
  26.     for(int i = 0; i< n; i++){
  27.         temp[i] = A[i];
  28.         visited[i] = 0;
  29.     }
  30.     sort(temp, temp + n);
  31.  
  32.     int index = 0;
  33.     for(int i = 0; i < m; i++){
  34.         int f = binarySearch(temp, 0, n-1, B[i]); // tìm vị trí đâu tiến của B[i] trong mảng temp
  35.         if(f == -1) continue; // nếu ko tìm thấy thì tiếp tục
  36.  
  37.         for(int j = f; (j<n && temp[j] == B[i]); j++){ 
  38.             A[index++] = temp[j];
  39.             visited[j] = 1; // đánh dấu đã thăm
  40.         }
  41.     }
  42.  
  43.     // điền nốt những phần tử ko có trong mảng B 
  44.     for(int i = 0; i< n; i++){
  45.         if(visited[i] == 0){
  46.             A[index++] = temp[i];
  47.         }
  48.     }
  49. }
  50.  
  51. void print(int A[], int n){
  52.     for(int i = 0; i< n; i++){
  53.         cout << A[i] <<" ";
  54.     }
  55.     cout << endl;
  56. }
  57.  
  58. int main(){
  59.     int t;
  60.     cin >> t;
  61.     while(t--){
  62.         int n, m;
  63.         cin >> n >> m;
  64.         int A[n], B[m];
  65.  
  66.         for(int i = 0; i < n; i++){
  67.             cin >> A[i];
  68.         }
  69.         for(int i = 0; i < m; i++){
  70.             cin >> B[i];
  71.         }
  72.         sortAccording(A, B, n, m);
  73.         print(A,n);
  74.     }
  75.     return 0;
  76. }
Success #stdin #stdout 0s 5572KB
comments (?)
stdin
copy 
1
11 4
2 1 2 5 7 1 9 3 6 8 8
2 1 8 3
stdout
copy 
2 2 1 1 8 8 3 5 6 7 9
https://ideone.com/3nFLAV
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!