YEZAELP

SMMR-246: Median (priority queue)

Jun 13th, 2021
873
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void prt(priority_queue <int> one, priority_queue <int, vector <int>, greater <int>> two){
  6.     while(one.size() > 0){
  7.         printf("%d ", one.top());
  8.         one.pop();
  9.     }
  10.     printf("\n");
  11.     while(two.size() > 0){
  12.         printf("%d ", two.top());
  13.         two.pop();
  14.     }
  15.     printf("\n");
  16. }
  17.  
  18. int main(){
  19.  
  20.     int n;
  21.     scanf("%d", &n);
  22.  
  23.     priority_queue <int> one;
  24.     priority_queue <int, vector <int>, greater <int>> two;
  25.  
  26.     int x1, x2;
  27.     scanf("%d%d", &x1, &x2);
  28.     printf("%d %d ", x1, (x1+x2)/2);
  29.     if(x1 < x2){
  30.         one.push(x1);
  31.         two.push(x2);
  32.     }
  33.     else{
  34.         one.push(x2);
  35.         two.push(x1);
  36.     }
  37.  
  38.     for(int i=3;i<=n;i++){
  39.         int x;
  40.         scanf("%d", &x);
  41.         if(i % 2 == 1){
  42.             if(x < two.top()){
  43.                 one.push(x);
  44.             }
  45.             else {
  46.                 one.push(two.top());
  47.                 two.pop();
  48.                 two.push(x);
  49.             }
  50.         }
  51.         else {
  52.             if(x > one.top()) two.push(x);
  53.             else {
  54.                 two.push(one.top());
  55.                 one.pop();
  56.                 one.push(x);
  57.             }
  58.         }
  59.         if(i % 2 == 1) printf("%d ", one.top());
  60.         else printf("%d ", (one.top() + two.top()) / 2);
  61.     }
  62.  
  63.     return 0;
  64. }
  65.  
RAW Paste Data