#include<bits/stdc++.h> #define ALL(X) X.begin(),X.end() #define FOR(I,A,B) for(int (I) = (A); (I) <= (B); (I)++) #define FORW(I,A,B) for(int (I) = (A); (I) < (B); (I)++) #define FORD(I,A,B) for(int (I) = (A); (I) >= (B); (I)--) #define CLEAR(X) memset(X,0,sizeof(X)) #define SIZE(X) int(X.size()) #define CONTAINS(A,X) (A.find(X) != A.end()) #define PB push_back #define MP make_pair #define X first #define Y second using namespace std; template<typename T, typename U> ostream& operator << (ostream& os, const pair<T, U> &_p) { return os << "(" << _p.X << "," << _p.Y << ")"; } template<typename T> ostream& operator << (ostream &os, const vector<T>& _V) { bool f = true; os << "["; for(auto v: _V) { os << (f ? "" : ",") << v; f = false; } return os << "]"; } template<typename T> ostream& operator << (ostream &os, const set<T>& _S) { bool f = true; os << "("; for(auto s: _S) { os << (f ? "" : ",") << s; f = false; } return os << ")"; } template<typename T, typename U> ostream& operator << (ostream &os, const map<T, U>& _M) { return os << set<pair<T, U>>(ALL(_M)); } typedef signed long long slong; typedef long double ldouble; typedef pair<int,int> pii; const slong INF = 1000000100; const ldouble EPS = 1e-9; template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";} template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...); } #ifdef LOCAL #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #define cerr if(0)cout #endif const int MAXN = 1000042; int cnt[MAXN+42]; void solve() { int n; cin >> n; FOR(i,1,n) { int a; cin >> a; cnt[a]++; } int ans = 0; FORW(i,0,MAXN) { cnt[i+1] += cnt[i] / 2; cnt[i] %= 2; if(cnt[i]) ans = i; } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); solve(); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include<bits/stdc++.h> #define ALL(X) X.begin(),X.end() #define FOR(I,A,B) for(int (I) = (A); (I) <= (B); (I)++) #define FORW(I,A,B) for(int (I) = (A); (I) < (B); (I)++) #define FORD(I,A,B) for(int (I) = (A); (I) >= (B); (I)--) #define CLEAR(X) memset(X,0,sizeof(X)) #define SIZE(X) int(X.size()) #define CONTAINS(A,X) (A.find(X) != A.end()) #define PB push_back #define MP make_pair #define X first #define Y second using namespace std; template<typename T, typename U> ostream& operator << (ostream& os, const pair<T, U> &_p) { return os << "(" << _p.X << "," << _p.Y << ")"; } template<typename T> ostream& operator << (ostream &os, const vector<T>& _V) { bool f = true; os << "["; for(auto v: _V) { os << (f ? "" : ",") << v; f = false; } return os << "]"; } template<typename T> ostream& operator << (ostream &os, const set<T>& _S) { bool f = true; os << "("; for(auto s: _S) { os << (f ? "" : ",") << s; f = false; } return os << ")"; } template<typename T, typename U> ostream& operator << (ostream &os, const map<T, U>& _M) { return os << set<pair<T, U>>(ALL(_M)); } typedef signed long long slong; typedef long double ldouble; typedef pair<int,int> pii; const slong INF = 1000000100; const ldouble EPS = 1e-9; template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";} template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) { while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...); } #ifdef LOCAL #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #define cerr if(0)cout #endif const int MAXN = 1000042; int cnt[MAXN+42]; void solve() { int n; cin >> n; FOR(i,1,n) { int a; cin >> a; cnt[a]++; } int ans = 0; FORW(i,0,MAXN) { cnt[i+1] += cnt[i] / 2; cnt[i] %= 2; if(cnt[i]) ans = i; } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); solve(); } |