D Merge Equals Educational Codeforces Round 42 (Rated for Div. 2) （STL ）
D. Merge Equals
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value x that occurs in the array 2 or more times. Take the first two occurrences of x in this array (the two leftmost occurrences). Remove the left of these two occurrences, and the right one is replaced by the sum of this two values (that is, 2⋅x).
Determine how the array will look after described operations are performed.
For example, consider the given array looks like [3,4,1,2,2,1,1]. It will be changed in the following way: [3,4,1,2,2,1,1] → [3,4,2,2,2,1] → [3,4,4,2,1] → [3,8,2,1].
If the given array is look like [1,1,3,1,1] it will be changed in the following way: [1,1,3,1,1] → [2,3,1,1] → [2,3,2] → [3,4].
Input
The first line contains a single integer n (2≤n≤150000) — the number of elements in the array.
The second line contains a sequence from n elements a1,a2,…,an (1≤ai≤109) — the elements of the array.
Output
In the first line print an integer k — the number of elements in the array after all the performed operations. In the second line print k integers — the elements of the array after all the performed operations.
Examples
inputCopy
7
3 4 1 2 2 1 1
outputCopy
4
3 8 2 1
inputCopy
5
1 1 3 1 1
outputCopy
2
3 4
inputCopy
5
10 40 20 50 30
outputCopy
5
10 40 20 50 30
Note
The first two examples were considered in the statement.
In the third example all integers in the given array are distinct, so it will not change.
题意：
思路：
用map标记一下当前数字是否已经出现了，并记录位置，从1到n扫一遍，每一次遇到一个 a[i] 之前已经出现了的时候，就把它和上一个a[i]合并为 a[i]2 ，并标记a[i] 为没有出现的状态（因为2个a[i] 组成 2a[i]了 ）并循环此过程，直到当前a[i] 的值是只有一个的。
细节见代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int *p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
std::vector<ll> v;
int n;
ll a[maxn];
map<ll, int> m;
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
gbtb;
cin >> n;
repd(i, 1, n) {
cin >> a[i];
}
repd(i, 1, n) {
while(m[a[i]] != 0) {
a[m[a[i]]] = 0;
m[a[i]]=0;
a[i]*=2;
}
m[a[i]] = i;
}
repd(i,1,n)
{
if(m[a[i]])
{
v.push_back(a[i]);
}
}
cout << sz(v) << endl;
for (auto x : v) {
cout << x << " ";
}
cout << endl;
return 0;
}
inline void getInt(int *p)
{
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
} else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
