#include <iostream> #include <vector> #include <algorithm> #include <tuple> int main() { using pa = std::pair<int,int>; int n; // 1 <= n <= 1000000 int x; // 0 <= x <= 201718 std::cin >> n; std::vector<pa> tab; tab.reserve(n); for (int i = 1; i <= n; ++i) { int x; std::cin >> x; tab.emplace_back(x, 1); } std::sort(tab.begin(), tab.end(), [](pa const & x, pa const & y){ return x.first > y.first;}); int a = 0; while (tab.size() > 0) { a = tab.back().first; int len = 0; while (tab.size() > 0 && tab.back().first == a) {len += tab.back().second; tab.pop_back();} if (len > 1) tab.emplace_back(a + 1, len/2); } std::cout << a << "\n"; return 0; }
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 | #include <iostream> #include <vector> #include <algorithm> #include <tuple> int main() { using pa = std::pair<int,int>; int n; // 1 <= n <= 1000000 int x; // 0 <= x <= 201718 std::cin >> n; std::vector<pa> tab; tab.reserve(n); for (int i = 1; i <= n; ++i) { int x; std::cin >> x; tab.emplace_back(x, 1); } std::sort(tab.begin(), tab.end(), [](pa const & x, pa const & y){ return x.first > y.first;}); int a = 0; while (tab.size() > 0) { a = tab.back().first; int len = 0; while (tab.size() > 0 && tab.back().first == a) {len += tab.back().second; tab.pop_back();} if (len > 1) tab.emplace_back(a + 1, len/2); } std::cout << a << "\n"; return 0; } |