// Task: a.cc // Created at Mon, Nov 20, 2017 4:13:24 PM #include <bits/stdc++.h> using namespace std; namespace { struct point_t; using i64 = int64_t; using u64 = uint64_t; #define all(x) begin(x),end(x) template<typename T = int> T read(); template<typename T = int> vector<T> read_vec(size_t const n); template<typename T>ostream& operator<<(ostream& os, vector<T> const vec); template<typename T> T gcd(T const a, T const b); } u64 highest_pow(u64 x) { for(int i=31; i>=0; --i) { if(x & (1 << i)) return i; } return 0; } int main(int, char**) { // cin.tie(nullptr); ios_base::sync_with_stdio(false); constexpr int MAXIMUM = 201718; auto a = read_vec<i64>(read()); vector<int> freq(MAXIMUM + 1, 0); for_each(all(a), [&](int x) {++freq[x]; }); i64 maxNonZero = [&](){ int res = 0; for(size_t i=0; i<freq.size()-1; ++i) { freq[i+1] += freq[i] / 2; freq[i] = freq[i] % 2; if(freq[i]) res = i; } return res; }(); cout << (freq[MAXIMUM] ? MAXIMUM + highest_pow(freq[MAXIMUM]) : maxNonZero) << '\n'; } /************************************************************************************************** ********************************* DEFINITIONS OF HELPER FUNCTIONS ******************************** **************************************************************************************************/ namespace { template<typename T = int> T read() { T x; cin >> x; return x; } template<typename T = int> vector<T> read_vec(size_t const n) { vector<T> vec(n); copy_n(istream_iterator<T>(cin), n, begin(vec)); return vec; } template<typename T> ostream& operator<<(ostream& os, vector<T> const vec) { copy(begin(vec), end(vec), ostream_iterator<T>(os, " ")); return os; } template<typename T> T gcd(T const a, T const b) { return a==0 ? b : gcd(b%a, a); } struct point_t { int x, y; point_t(int _x, int _y) : x{_x}, y{_y} {} friend istream& operator>>(istream& is, point_t& p) { is>>p.x>>p.y; return is; } }; }
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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | // Task: a.cc // Created at Mon, Nov 20, 2017 4:13:24 PM #include <bits/stdc++.h> using namespace std; namespace { struct point_t; using i64 = int64_t; using u64 = uint64_t; #define all(x) begin(x),end(x) template<typename T = int> T read(); template<typename T = int> vector<T> read_vec(size_t const n); template<typename T>ostream& operator<<(ostream& os, vector<T> const vec); template<typename T> T gcd(T const a, T const b); } u64 highest_pow(u64 x) { for(int i=31; i>=0; --i) { if(x & (1 << i)) return i; } return 0; } int main(int, char**) { // cin.tie(nullptr); ios_base::sync_with_stdio(false); constexpr int MAXIMUM = 201718; auto a = read_vec<i64>(read()); vector<int> freq(MAXIMUM + 1, 0); for_each(all(a), [&](int x) {++freq[x]; }); i64 maxNonZero = [&](){ int res = 0; for(size_t i=0; i<freq.size()-1; ++i) { freq[i+1] += freq[i] / 2; freq[i] = freq[i] % 2; if(freq[i]) res = i; } return res; }(); cout << (freq[MAXIMUM] ? MAXIMUM + highest_pow(freq[MAXIMUM]) : maxNonZero) << '\n'; } /************************************************************************************************** ********************************* DEFINITIONS OF HELPER FUNCTIONS ******************************** **************************************************************************************************/ namespace { template<typename T = int> T read() { T x; cin >> x; return x; } template<typename T = int> vector<T> read_vec(size_t const n) { vector<T> vec(n); copy_n(istream_iterator<T>(cin), n, begin(vec)); return vec; } template<typename T> ostream& operator<<(ostream& os, vector<T> const vec) { copy(begin(vec), end(vec), ostream_iterator<T>(os, " ")); return os; } template<typename T> T gcd(T const a, T const b) { return a==0 ? b : gcd(b%a, a); } struct point_t { int x, y; point_t(int _x, int _y) : x{_x}, y{_y} {} friend istream& operator>>(istream& is, point_t& p) { is>>p.x>>p.y; return is; } }; } |