CodeForces 305C Ivan and Powers of Two

First of all, let's carry over all powers of two in the following way: if we have ai = aj</span>, i ≠ j, carry 1 to ai + 1</span>. Now as all of ai</span> are distinct, the answer is max(ai)</span> — cnt(ai)</span> + 1, where max(ai)</span> — maximal value of ai</span>,cnt(ai)</span> — size of a

因为从小到大输入SET所以能够保证总是distinct。

/* From: Lich_Amnesia
 * Time: 2014-01-24 14:23:29
 *
 *
 * */
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl

set<int>Set;
int main(){
	int n,cnt,Max = 0;
	cin >> n;
	for (int i = 0; i < n; i ++){
		cin >> cnt;
		while (Set.count(cnt)) Set.erase(cnt),cnt++;
		Set.insert(cnt);
		Max = max(Max,cnt);
	}
	cout << Max - Set.size() + 1 << endl;
	return 0;
}