#include <bits/stdc++.h>
#include <cstdio>
#pragma GCC optimize("O3")
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi = 3.14159265359;
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 262144 + 10;
inline int readint(){
int ret=0;
for(char c;;){
c=getchar();
if('0'<=c and c<='9')
ret=ret*10+(c&15);
else
return ret;
}
}
vector<char> digits;
inline void printint(int x){
do{
digits.push_back(x%10|48);
x/=10;
}while(x);
while(not digits.empty())
putchar(digits.back()), digits.pop_back();
}
int n;
int a[mxn];
//vector<int> f[mxn][40];
vector<vector<int> > f[mxn];
//map<int, vector<int> > f[mxn];
int p, l;
int p2;
int mi;
void combine(vector<int> &v1, vector<int> &v2, vector<int> &r){
p = 0;
p2 = 1;
l = 1;
while(p < (int)v1.size()){
fr(k, 0, l){
r[p2++] = v1[p+k];
}
fr(k, 0, l){
r[p2++] = v2[p+k];
}
p += l;
l *= 2;
}
}
vector<int> g1;
vector<int> g2;
vector<int> cand;
vector<int> nw;
void rec(int k){
cand.pb(a[k]);
if(k != 1){
if(k%2) cand.pb(a[k-1]);
else cand.pb(a[k+1]);
}
int sz = cand.size();
if(k*2 > n){
fr(i, 0, sz){
f[k].pb({cand[i]});
}
cand.pop_back();
if(k != 1){
cand.pop_back();
}
return;
}
rec(k*2);
rec(k*2+1);
f[k].resize(sz);
fr(j, 0, sz){
mi = min(cand[j], min(a[k*2], a[k*2+1]));
f[k][j].resize(2*(int)f[k*2][j].size()+1);
if(cand[j] == mi){
f[k][j][0] = mi;
combine(f[k*2][sz], f[k*2+1][sz], f[k][j]);
}
else if(a[k*2] == mi){
f[k][j][0] = mi;
combine(f[k*2][j], f[k*2+1][sz], f[k][j]);
}
else{
g1.resize(2*(int)f[k*2][j].size()+1);
g1[0] = mi;
combine(f[k*2][sz], f[k*2+1][j], g1);
g2.resize(2*(int)f[k*2][j].size()+1);
g2[0] = mi;
combine(f[k*2][j], f[k*2+1][sz+1], g2);
f[k][j] = min(g1, g2);
}
}
/*
for(auto j : cand){
mi = min(j, min(a[k*2], a[k*2+1]));
f[k][j].resize(2*(int)f[k*2][j].size()+1);
if(j == mi){
f[k][j][0] = mi;
combine(f[k*2][a[k*2]], f[k*2+1][a[k*2+1]], f[k][j]);
}
else if(a[k*2] == mi){
f[k][j][0] = mi;
combine(f[k*2][j], f[k*2+1][a[k*2+1]], f[k][j]);
}
else{
g1.resize(2*(int)f[k*2][j].size()+1);
g1[0] = mi;
combine(f[k*2][a[k*2]], f[k*2+1][j], g1);
g2.resize(2*(int)f[k*2][j].size()+1);
g2[0] = mi;
combine(f[k*2][j], f[k*2+1][a[k*2]], g2);
f[k][j] = min(g1, g2);
}
}*/
cand.pop_back();
if(k != 1){
cand.pop_back();
}
f[2*k].clear();
f[2*k+1].clear();
}
void solve(){
n = readint();
fr(i, 1, n+1){
a[i] = readint();
}
int orgn = n;
int m = n;
while(m+1 - ((m+1)&-(m+1)) != 0){
++m;
}
fr(i, n+1, m+1){
a[i] = i;
}
n = m;
rec(1);
vector<int> ans = f[1][0];
fr(i, 0, orgn){
printint(ans[i]);
putchar(' ');
}
}
int main(){
digits.reserve(10);
freopen("t.in.25", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:209:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
209 | freopen("t.in.25", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
6348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
6348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
6348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
6348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
6348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
