Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <math.h>
- #include <sstream>
- #include <string>
- #include <iostream>
- #include <limits>
- #include <stdexcept>
- #include <unordered_set>
- #include <unordered_map>
- #include <vector>
- #include <string>
- #include <map>
- #include <set>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cstdlib>
- #include <numeric>
- #include <array>
- #include <iomanip> // std::setprecision
- #include <tuple>
- #include <iostream>
- #include <fstream>
- using namespace std;
- #define int int64_t
- int32_t main() { //== Merge Equals
- /*
- https://codeforces.com/group/Ap6SQK7app/contest/309423/problem/E
- https://codeforces.com/problemset/problem/962/D
- data structures
- implementation *1600
- 7
- 3 4 1 2 2 1 1
- 4
- 3 8 2 1
- */
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- int N;
- cin >> N;
- vector<int> a(N, -1);
- map< int, set<int> > dupLists; // orderedMap === { value : { all positinos of this value, in accending order } }
- for(int i = 0; i < N; ++i) {
- int c;
- cin >> c;
- a[i] = c;
- dupLists[c].insert(i);
- }
- for( auto it = dupLists.begin(); it != dupLists.end(); ) { //== G_searched
- /*for (auto it2 = dupLists.begin(); it2 != dupLists.end(); it2++) {
- if (it == it2) {
- cerr << "-> ";
- }
- cerr << it2->first << ": ";
- for (int pos: it2->second) {
- cerr << pos << ' ';
- }
- cerr << endl;
- }
- cerr << endl;*/
- auto& lst = it->second;
- if( lst.size() > 1 ){ //== the first ( smallest ) key, who has duplictes
- int leftDupPos = *lst.begin();
- int rightDupPos = *(++lst.begin()); //== the right side of duplicate's position
- //cerr << "!!! " << leftDupPos << ' ' << rightDupPos << endl;
- lst.erase(leftDupPos);
- a[leftDupPos] = -1; //== mark a removed position
- lst.erase(rightDupPos);
- a[rightDupPos] *= 2;
- dupLists[a[rightDupPos]].insert(rightDupPos);
- } else {
- it++;
- }
- }
- //== how about output ?
- int remainTotal = 0;
- for(auto ele : a) {
- if( ele > 0 ){
- remainTotal++;
- }
- }
- cout << remainTotal << endl;
- for( auto ele : a){
- if( ele > 0 ){
- cout << ele << " ";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment