| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 520247 | 2022-01-29T02:12:35 Z | christinelynn | Swap (BOI16_swap) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y cout<<y,exit(0
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e9 + 7;
vector<ll> dp[N[18[2;
ll n,a[N;
bool need[N[18[2;
void Merge(vector<ll> &res,vector<ll> &a,vector<ll> &b{
for (ll i = 0,j = 1;i < a.size(;i += j,j *= 2{
for (ll k = i;k < i + j && k < a.size(;k++ res.push_back(a[k;
for (ll k = i;k < i + j && k < b.size(;k++ res.push_back(b[k;
int main({
ios_base::sync_with_stdio(NULL; cin.tie(0; cout.tie(0;
#define task "test"
if (fopen(task".inp","r"{
freopen(task".inp","r",stdin;
//freopen(task".out","w",stdout;
cin>>n;
for (ll i = 1;i <= n;i++ cin>>a[i;
need[1[0[1 = 1;
for (ll node = 1;node <= n/2;node++{
for (ll i = 0;node >> i;i++{
for (auto j : {0,1{
if (!need[node[i[j continue;
ll p = ((node >> i + 1 << 1 + j;
ll mn = min({a[p,a[node*2,a[node*2 + 1;
if (mn == a[node*2
need[2*node[i + 1[j = need[2*node + 1[0[1 = 1;
else if (mn == a[p
need[2*node[0[0 = need[2*node + 1[0[1 = 1;
else
need[2*node[0[0 = need[2*node + 1[0[0 = 1,
need[2*node[i + 1[j = need[2*node + 1[i + 1[j = 1;
for (ll node = n;node;node--{
for (ll i = 0;node >> i;i++{
for (auto j : {0,1{
if (!need[node[i[j continue;
ll p = ((node >> i + 1 << 1 + j;
if (2*node > n dp[node[i[j = {a[p;
else if (2*node == n dp[node[i[j = {min(a[p,a[node*2,max(a[p,a[node*2;
else{
ll mn = min({a[p,a[2*node,a[2*node + 1;
if (mn == a[2*node + 1{
vector<ll> tmp1,tmp2; tmp1 = tmp2 = {a[2*node + 1;
Merge(tmp1,dp[2*node[0[0,dp[2*node + 1[i + 1[j;
Merge(tmp2,dp[2*node[i + 1[j,dp[2*node + 1[0[0;
dp[node[i[j = min(tmp1,tmp2;
else{
dp[node[i[j = {min(a[p,a[2*node;
if (mn == a[p
Merge(dp[node[i[j,dp[2*node[0[0,dp[2*node + 1[0[1;
else
Merge(dp[node[i[j,dp[2*node[i + 1[j,dp[2*node + 1[0[1;
if (2*node < n{
for (ll i = 0;2*node >> i;i++{
for (auto j : {0,1
vector<ll>(.swap(dp[2*node[i[j,
vector<ll>(.swap(dp[2*node + 1[i[j;
for (auto i : dp[1[0[1 cout<<i<<" ";
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/)]]])]]]))]]]))})
})
})]]]]]]]]])]]]]]]]]])])]])}]]]
})]]]]]]]]])]]]]]])]}
}])]]]})
}]])]])}]]])]}]]])))]]])
}})
})
})]]]]]]]]]]]]]]]]]]])]]]]]]])]]]})))]]])
}})
})
})]]]])))
})))))
})])))])))
}))
})]]]]]]]))