rembocoder

Untitled

Apr 28th, 2023
902
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.47 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <sstream>
  4. #include <string>
  5. #include <iostream>
  6. #include <limits>
  7. #include <stdexcept>
  8. #include <unordered_set>
  9. #include <unordered_map>
  10. #include <vector>
  11. #include <string>
  12. #include <map>
  13. #include <set>
  14. #include <stack>
  15. #include <queue>
  16. #include <algorithm>
  17. #include <cstdlib>
  18. #include <numeric>
  19. #include <array>
  20. #include <iomanip>      // std::setprecision
  21. #include <tuple>
  22. #include <iostream>
  23. #include <fstream>
  24.  
  25. using namespace std;
  26.  
  27. #define int int64_t
  28.  
  29. int32_t main() { //== Merge Equals
  30.     /*
  31.      https://codeforces.com/group/Ap6SQK7app/contest/309423/problem/E
  32.      https://codeforces.com/problemset/problem/962/D
  33.      data structures
  34.      implementation *1600
  35.  
  36.      7
  37.      3 4 1 2 2 1 1
  38.  
  39.      4
  40.      3 8 2 1
  41.  
  42.      */
  43.     ios_base::sync_with_stdio(false);
  44.     cin.tie(0); cout.tie(0);
  45.     int N;
  46.     cin >> N;
  47.     vector<int> a(N, -1);
  48.     map< int, set<int> > dupLists; // orderedMap === { value : { all positinos of this value, in accending order } }
  49.     for(int i = 0; i < N; ++i) {
  50.         int c;
  51.         cin >> c;
  52.         a[i] = c;
  53.         dupLists[c].insert(i);
  54.     }
  55.  
  56.     for( auto it = dupLists.begin(); it != dupLists.end(); ) { //== G_searched
  57.         /*for (auto it2 = dupLists.begin(); it2 != dupLists.end(); it2++) {
  58.             if (it == it2) {
  59.                 cerr << "-> ";
  60.             }
  61.             cerr << it2->first << ": ";
  62.             for (int pos: it2->second) {
  63.                 cerr << pos << ' ';
  64.             }
  65.             cerr << endl;
  66.         }
  67.         cerr << endl;*/
  68.         auto& lst = it->second;
  69.         if( lst.size() > 1 ){ //== the first ( smallest ) key, who has duplictes
  70.             int leftDupPos = *lst.begin();
  71.             int rightDupPos = *(++lst.begin()); //== the right side of duplicate's position
  72.             //cerr << "!!! " << leftDupPos << ' ' << rightDupPos << endl;
  73.             lst.erase(leftDupPos);
  74.             a[leftDupPos] = -1; //== mark a removed position
  75.             lst.erase(rightDupPos);
  76.             a[rightDupPos] *= 2;
  77.             dupLists[a[rightDupPos]].insert(rightDupPos);
  78.         } else {
  79.             it++;
  80.         }
  81.     }
  82.     //== how about output ?
  83.     int remainTotal = 0;
  84.     for(auto ele : a) {
  85.         if( ele > 0 ){
  86.             remainTotal++;
  87.         }
  88.     }
  89.     cout << remainTotal << endl;
  90.     for( auto ele : a){
  91.         if( ele > 0 ){
  92.             cout << ele << " ";
  93.         }
  94.     }
  95.  
  96.     return 0;
  97. }
  98.  
Advertisement
Add Comment
Please, Sign In to add comment