Advertisement
ProgramoBien

P16175 F002B. Compressed vectors

Dec 11th, 2017
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. struct Pair {
  7.     int value;
  8.     int pos;
  9. };
  10.  
  11. typedef vector<Pair> Com_Vec;
  12.  
  13. Com_Vec sum(const Com_Vec& v1, const Com_Vec& v2){
  14.     int a, b, s1 = v1.size(), s2 = v2.size();
  15.     a = b = 0;
  16.     Com_Vec v;
  17.     while(a < s1 or b < s2){
  18.         Pair p;
  19.         if(a < s1 and b < s1){
  20.             Pair p1 = v1[a], p2 = v2[b];
  21.             if(p1.pos == p2.pos){
  22.                 p.pos = p1.pos;
  23.                 p.value = p1.value + p2.value;
  24.                 ++a;
  25.                 ++b;
  26.             }
  27.             else if(p1.pos < p2.pos){
  28.                 p.pos = p1.pos;
  29.                 p.value = p1.value;
  30.                 ++a;
  31.             }
  32.             else if(p2.pos < p1.pos){
  33.                 p.pos = p2.pos;
  34.                 p.value = p2.value;
  35.                 ++b;
  36.             }
  37.         }
  38.         else if(a < s1){
  39.             Pair p1 = v1[a];
  40.             p.pos = p1.pos;
  41.             p.value = p1.value;
  42.             ++a;
  43.         }
  44.         else if(b < s2){
  45.             Pair p2 = v2[b];
  46.             p.pos = p2.pos;
  47.             p.value = p2.value;
  48.             ++b;
  49.         }
  50.         if(p.value != 0) v.push_back(p);
  51.     }
  52.     return v;
  53. }
  54.  
  55. void p(const Com_Vec& v){
  56.     int l = v.size();
  57.     cout << l;
  58.     for(int i = 0; i < l; ++i){
  59.         cout << " " << v[i].value << ";" << v[i].pos;
  60.     }
  61.     cout << endl;
  62. }
  63.  
  64. void read(Com_Vec& v){
  65.     int n;
  66.     cin >> n;
  67.     Com_Vec cv(n);
  68.     int i = 0;
  69.     if(n == 0){
  70.         Pair r;
  71.         r.pos = 1;
  72.         r.value = 0;
  73.         cv.push_back(r);
  74.     }
  75.     while(n--){
  76.         char c;
  77.         cin >> cv[i].value >> c >> cv[i].pos;
  78.         ++i;
  79.     }
  80.  
  81.     v = cv;
  82. }
  83.  
  84. int main() {
  85.     int k;
  86.     cin >> k;
  87.     vector< Com_Vec> vc(2);
  88.     while(k--){
  89.         read(vc[0]);
  90.         read(vc[1]);
  91.         Com_Vec v = sum(vc[0], vc[1]);
  92.         p(v);
  93.     }
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement