#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
using namespace std;
int N = 201719;
int* t = new int[N];
int curr_i = 0;
int max_idx = 0;
int maxI = 0;
void shift(int* t) {
for (int i = 0; i <= max_idx; i++) {
t[i] = t[i+1];
}
}
void add(int a) {
int i = a - curr_i;
max_idx = max(i, max_idx);
int v = t[i];
if(v == 0) {
t[i] = 1;
maxI = max(maxI, i+curr_i);
} else if (v == 1) {
t[i] = 0;
add(a+1);
}
}
int main(int argc, const char* argv[]) {
size_t n;
cin >> n;
std::vector<int> vs (n);
for(int i = 0; i < n; i++ ) {
string a;
cin >> a;
vs[i] = stoi(a);
}
std::sort(vs.begin(), vs.end());
for(auto v : vs) {
if(curr_i < v) {
shift(t);
curr_i = v;
}
add(v);
}
cout << maxI << endl;
}
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 | #include <iostream> #include <cmath> #include<vector> #include <algorithm> using namespace std; int N = 201719; int* t = new int[N]; int curr_i = 0; int max_idx = 0; int maxI = 0; void shift(int* t) { for (int i = 0; i <= max_idx; i++) { t[i] = t[i+1]; } } void add(int a) { int i = a - curr_i; max_idx = max(i, max_idx); int v = t[i]; if(v == 0) { t[i] = 1; maxI = max(maxI, i+curr_i); } else if (v == 1) { t[i] = 0; add(a+1); } } int main(int argc, const char* argv[]) { size_t n; cin >> n; std::vector<int> vs (n); for(int i = 0; i < n; i++ ) { string a; cin >> a; vs[i] = stoi(a); } std::sort(vs.begin(), vs.end()); for(auto v : vs) { if(curr_i < v) { shift(t); curr_i = v; } add(v); } cout << maxI << endl; } |
English