| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 734152 | minhcool | 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.
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = `e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n;
int arr[N];
// if initially arr[i] = j, what is the minimum array?
vector<int> dp[N][35];
map<int, int> mp[N];
vector<int> merge(vector<int> a, vector<int> b, int i){
vector<int> c(a.size() + b.size());
int itr1 = 0, itr2 = 0, itr3 = 0;
queue<pair<int, bool>> q;
q.push({i << 1, 0}), q.push({i << 1 | 1, 1});
while(!q.empty()){
int u = q.front().fi, type = q.front().se;
q.pop();
if(!type){
c[itr3] = a[itr1];
itr1++, itr3++;
}
else{
c[itr3] = b[itr2];
itr2++, itr3++;
}
if((u << 1) <= n) q.push({(u << 1), (bool)type});
if((u << 1 | 1) <= n) q.push({(u << 1 | 1), (bool)type});
}
return c;
/*
while(itr1 < a.size() || itr2 < b.size()){
if(itr1 == a.size()){
c.pb(b[itr2]);
itr2++;
}
else if(itr2 == b.size()){
c.pb(a[itr1]);
itr1++;
}
else if(a[itr1].fi < b[itr2].fi){
c.pb(a[itr1]);
itr1++;
}
else{
c.pb(b[itr2]);
itr2++;
}
}*/
return c;
}
void ins(int i, int j){
if(mp[i].find(j) != mp[i].end()) return;
mp[i][j] = 0;
mp[i][j] = mp[i].size();
}
void process(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
//cout << "OK\n";
//return;
for(int i = 1; i <= n; i++){
int itr = i;
mp[i][arr[i]] = 1;
while(itr != 1){
itr /= 2;
ins(i, arr[itr]);
ins(i, arr[itr << 1]);
ins(i, arr[itr << 1 | 1]);
//if(itr == 1) break;
}
}
//return;
for(int i = n; i >= 1; i--){
if(i * 2 > n){
//for(int j = 1; j <= n; j++) dp[i][j].pb({i, j});
for(auto it : mp[i]) dp[i][it.se].pb(it.fi);
}
else if(i * 2 + 1 > n){
for(auto it : mp[i]){
int j = it.fi;
//if(j == arr[i * 2]) continue;
dp[i][it.se].pb(min(j, arr[i * 2]));
dp[i][it.se].pb(max(j, arr[i * 2]));
}
}
else{//continue;
for(auto it1 : mp[i]){
int ind = it1.se, j = it1.fi;
int temp = min(j, min(arr[i * 2], arr[i * 2 + 1]));
//cout << i << " " << j << " " << temp << "\n";
if(temp == j){// no swapping
int temp1 = mp[i * 2][arr[i * 2]], temp2 = mp[i * 2 + 1][arr[i * 2 + 1]];
vector<int> temp = merge(dp[i * 2][temp1], dp[i * 2 + 1][temp2], i);
dp[i][ind].pb(j);
for(auto it : temp) dp[i][ind].pb(it);
}
else if(temp == arr[i * 2]){
//cout << "OK\n";
int temp1 = mp[i * 2 + 1][arr[i * 2 + 1]], temp2 = mp[i * 2][j];
vector<int> temp = merge(dp[i * 2][temp2], dp[i * 2 + 1][temp1], i);
dp[i][ind].pb(arr[i * 2]);
for(auto it : temp) dp[i][ind].pb(it);
}
else{
//continue;
int tempo1 = mp[i * 2 + 1][arr[i * 2]], tempo2 = mp[i * 2][arr[i * 2]];
vector<int> temp1 = merge(dp[i * 2][mp[i * 2][j]], dp[i * 2 + 1][tempo1], i), temp2 = merge(dp[i * 2][tempo2], dp[i * 2 + 1][mp[i * 2 + 1][j]], i);
dp[i][ind].pb(arr[i * 2 + 1]);
bool ck = 0;
assert(temp1.size() == temp2.size());
for(int i = 0; i < temp1.size(); i++){
//assert(temp1[i].fi == temp2[i].fi);
if(temp1[i] != temp2[i]){
ck = (temp1[i] < temp2[i]);
break;
}
}
if(!ck) for(auto it : temp2) dp[i][ind].pb(it);
else for(auto it : temp1) dp[i][ind].pb(it);
}
}
for(int j = 1; j <= mp[i * 2].size(); j++) dp[i * 2][j].clear();
for(int j = 1; j <= mp[i * 2 + 1].size(); j++) dp[i * 2 + 1][j].clear();
}
}
for(auto it : dp[1][mp[1][arr[1]]]) cout << it << " ";
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}