| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 563348 |
2022-05-17T02:24:01 Z |
tranxuanbach |
Swap (BOI16_swap) |
C++17 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;
const int N = 2e5 + 5;
bool debug = 0;
int n;
int a[N];
int ans[N];
int willgoup[N];
int b[N]; // b[i] will go up and stay at i
int valdfs[N]; bool changedfs[N];
int dfs(int i){ // find the lowest index if start at i
if (debug) cout << "dfs " << i << endl;
if (!changedfs[i]){
return valdfs[i];
}
if (b[i] == -1 or b[i] == 0){
return (valdfs[i] = i);
}
if (willgoup[i * 2] == 1){
return (valdfs[i] = dfs(i * 2));
}
if (willgoup[i * 2] == 0){
return (valdfs[i] = dfs(i * 2 + 1));
}
return (valdfs[i] = min(dfs(i * 2), dfs(i * 2 + 1)));
}
void dfs_assign(int i, int j){
if (debug) cout << "dfs_assign " << i << ' ' << j << endl;
changedfs[i] = 1;
if (i == j){
if (i * 2 <= n){
willgoup[i * 2] = 0;
}
if (i * 2 + 1 <= n){
willgoup[i * 2 + 1] = 0;
}
b[i] = -1;
return;
}
if (willgoup[i * 2] == 1){
dfs_assign(i * 2, j);
return;
}
if (willgoup[i * 2] == 0){
dfs_assign(i * 2 + 1, j);
return;
}
if (valdfs[i * 2] == j){
willgoup[i * 2] = 1;
dfs_assign(i * 2, j);
}
else{
willgoup[i * 2] = 0;
dfs_assign(i * 2 + 1, j);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n;
ForE(i, 1, n){
cin >> a[i];
}
ForE(i, 1, n){
willgoup[i] = -1;
b[i] = -1;
changedfs[i] = 1;
}
willgoup[1] = 0;
vpii aa;
ForE(i, 1, n){
aa.emplace_back(a[i], i);
}
sort(bend(aa));
Fora(elem, aa){
int val, idx; tie(val, idx) = elem;
if (debug) cout << "elem " << val << ' ' << idx << endl;
if (willgoup[idx] != 0 and b[idx / 2] == -1){
if (debug) cout << "fix up " << endl;
willgoup[idx] = 1;
if (idx % 2 == 0){
willgoup[idx + 1] = 0;
}
b[idx / 2] = idx;
ans[idx / 2] = val;
continue;
}
int pos = n + 1, u = -1;
if (willgoup[idx] != 1){
int tpos = dfs(idx);
if (debug) cout << "case 1 " << tpos << endl;
if (pos > tpos){
pos = tpos;
u = idx;
}
}
if (idx % 2 == 0 and willgoup[idx] != 0){
int tpos = dfs(idx + 1);
if (debug) cout << "case 2 " << tpos << endl;
if (pos > tpos){
pos = tpos;
u = idx + 1;
}
}
if (debug) cout << "ans " << pos << endl;
ans[pos] = val;
dfs_assign(u, pos);
}
ForE(i, 1, n){
cout << ans[i] << ' ';
} cout << endl;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
