#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;
void debug(string names) {
cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
int pos = 0;
for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
cout << names[pos];
cout << ": " << par << " ";
while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
pos++;
}
names.erase(names.begin(), names.begin() + pos);
debug(names, left...);
}
struct fenwick {
int n;
vector<int> tree;
fenwick() {}
fenwick(int sz) {
n = sz + 1;
tree.resize(n, 0);
}
void upd(int pos) {
for (pos++; pos <= n; pos += (pos & -pos)) tree[pos]++;
}
int query(int pos) {
int rtn = 0;
for (pos++; pos; pos -= (pos & -pos)) rtn += tree[pos];
return rtn;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
};
int n, a[100005], used[200005] = {}, ans[200005];
int L, R;
fenwick F;
int nxtl() {
while (used[L]) L++;
return L;
}
int nxtr() {
while (used[R]) R--;
return R;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
F = fenwick(2 * n);
for (int i = 0; i < n; i++) cin >> a[i], --a[i];
L = 0, R = 2 * (n - 1);
ans[0] = a[0];
used[ans[0]] = 1;
F.upd(ans[0]);
for (int i = 1; i < n; i++) {
int cur = F.query(a[i] - 1);
if (!used[a[i]]) {
ans[2 * i - 1] = a[i];
used[ans[2 * i - 1]] = 1;
F.upd(ans[2 * i - 1]);
if (cur == i - 1) {
ans[2 * i] = nxtl();
}
else {
ans[2 * i] = nxtr();
}
used[ans[2 * i]] = 1;
F.upd(ans[2 * i]);
}
else {
if (cur == i - 2) {
ans[2 * i - 1] = nxtl();
used[ans[2 * i - 1]] = 1;
F.upd(ans[2 * i - 1]);
ans[2 * i] = nxtl();
used[ans[2 * i]] = 1;
F.upd(ans[2 * i]);
}
else if (cur == i) {
ans[2 * i - 1] = nxtr();
used[ans[2 * i - 1]] = 1;
F.upd(ans[2 * i - 1]);
ans[2 * i] = nxtr();
used[ans[2 * i]] = 1;
F.upd(ans[2 * i]);
}
else {
ans[2 * i - 1] = nxtl();
used[ans[2 * i - 1]] = 1;
F.upd(ans[2 * i - 1]);
ans[2 * i] = nxtr();
used[ans[2 * i]] = 1;
F.upd(ans[2 * i]);
}
}
}
for (int i = 0; i < 2 * n - 1; i++) cout << 1 + ans[i] << " "; cout << '\n';
}
Compilation message
medians.cpp: In function 'int main()':
medians.cpp:110:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int i = 0; i < 2 * n - 1; i++) cout << 1 + ans[i] << " "; cout << '\n';
^~~
medians.cpp:110:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i = 0; i < 2 * n - 1; i++) cout << 1 + ans[i] << " "; cout << '\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
4 ms |
632 KB |
Output is correct |
| 4 |
Correct |
6 ms |
888 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1784 KB |
Output is correct |
| 6 |
Correct |
21 ms |
2936 KB |
Output is correct |
| 7 |
Correct |
34 ms |
4404 KB |
Output is correct |
