| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 706447 | ParsaS | Swap (BOI16_swap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the name of God
// : )
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4e5 + 5, MOD = 1e9 + 7, inf = 1e9 + 10;
int n, a[N], b[N], par[N];
void solve() {
cin >> n// In the name of God
// : )
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4e5 + 5, MOD = 1e9 + 7, inf = 1e9 + 10;
int n, a[N], par[N];
set<int> st[N];
void ins(int v, int x) {
st[v].insert(x);
}
void ers(int v, int x) {
st[v].erase(st[v].find(x));
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
par[i] = i / 2;
st[i].insert(a[i]);
st[i].insert(inf);
}
for (int i = n + 1; i <= 2 * n + 1; i++) {
st[i].insert(inf);
st[i].insert(inf - 1);
a[i] = inf - 1;
}
if (n <= 3) {
sort(a, a + n + 1);
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
return;
}
if (a[1] < min(a[2], a[3])) {
par[2] = par[3] = 0;
}
else if (a[2] < min(a[1], a[3])) {
ers(2, a[2]), ins(2, a[1]);
a[1] = a[2];
par[2] = par[3] = 0;
}
else {
ins(1, a[2]);
ers(2, a[2]);
ers(3, a[3]);
a[1] = a[3];
}
for (int i = 2; i <= n; i++) {
int lc = a[2 * i], rc = a[2 * i + 1];
int ul = 2 * i, ur = 2 * i + 1;
int v = i, mn = inf;
while (v) {
mn = min(mn, *st[v].begin());
v = par[v];
}
if (mn < min(lc, rc)) {
v = i;
while (!st[v].count(mn))
v = par[v];
ers(v, mn);
a[i] = mn;
par[ul] = par[ur] = 0;
}
else if (lc < min(mn, rc)) {
ers(ul, lc);
a[i] = lc;
par[rc] = 0;
}
else {
ers(ul, a[ul]);
ers(ur, a[ur]);
ins(i, lc);
a[i] = rc;
}
}
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1; //cin >> tc;
while (tc--) {
solve();
}
return 0;
}
;
for (int i = 1; i <= n; i++) {
cin >> a[i];
par[i] = i / 2;
b[i] = a[i];
}
for (int i = n + 1; i <= 2 * n + 1; i++)
b[i] = inf;
if (n <= 3) {
sort(a, a + n + 1);
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
return;
}
if (a[1] < min(a[2], a[3])) {
par[2] = par[3] = 0;
}
else if (a[2] < min(a[1], a[3])) {
a[1] = a[2];
b[2] = b[1];
par[2] = par[3] = 0;
}
else {
b[0] = a[1];
b[1] = b[2];
b[2] = b[3] = inf;
a[1] = a[3];
}
for (int i = 2; i <= n; i++) {
int lc = b[2 * i], rc = b[2 * i + 1];
int ul = 2 * i, ur = 2 * i + 1;
int v = i, mn = b[0];
while (v) {
mn = min(mn, b[v]);
v = par[v];
}
if (mn < min(lc, rc)) {
a[i] = mn;
v = i;
while (b[v] != mn)
v = par[v];
b[v] = inf;
par[ul] = par[ur] = 0;
}
else if (lc < min(mn, rc)) {
a[i] = lc;
b[lc] = inf;
par[rc] = 0;
}
else {
a[i] = rc;
b[i] = lc;
b[ur] = inf;
b[ul] = inf;
}
}
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1; //cin >> tc;
while (tc--) {
solve();
}
return 0;
}