| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 868748 |
2023-11-01T22:49:02 Z |
hazzle |
Swap (BOI16_swap) |
C++17 |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mt t make_tuple
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;
template <typename T>
using prq = priority_queue <T>;
template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;
template <typename T>
using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ook order_of_key
template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }
inline int solve(){
int n; cin >> n;
vec <int> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
auto mrg = [&](int x, vec <int> lf, vec <int> rt){
vec <int> res(1 + sz(lf) + sz(rt));
res[0] = x;
int p1 = 0, p2 = 0;
int st = 1, pt = 1;
while(pt < sz(res)){
for (int i = 0; i < st && p1 < sz(lf) && pt < sz(res); ++i){
res[pt++] = lf[p1++];
}
for (int i = 0; i < st && p2 < sz(rt) && pt < sz(res); ++i){
res[pt++] = rt[p2++];
}
st <<= 1;
}
return res;
};
vec <set <int>> val(n + 1);
auto ini = [&](auto &&ini, int i, int ai) -> void{
if (val[i].count(ai)) return;
val[i].insert(ai);
int ls = 2 * i, rs = 2 * i + 1;
if (ls > n) return;
if (rs > n) return;
if (ai < min(a[ls], a[rs])){
ini(ini, ls, a[ls]), ini(ini, rs, a[rs]);
}
else if (a[ls] < a[rs]){
ini(ini, ls, ai), ini(ini, rs, a[rs]);
}
else{
ini(ini, ls, a[ls]), ini(ini, rs, ai);
ini(ini, ls, ai), ini(ini, rs, a[ls]);
}
};
ini(ini, 1, a[1]);
vec <map <int, vec <int>>> dp(n + 1);
for (int i = n; i > 0; --i){
for (auto &ai: val[i]){
int ls = 2 * i, rs = 2 * i + 1;
if (ls > n){
dp[i][ai] = {ai};
continue;
}
if (rs > n){
dp[i][ai] = {min(ai, a[ls]), max(ai, a[ls])};
continue;
}
if (ai < min(a[ls], a[rs])){
dp[i][ai] = mrg(ai, dp[ls][a[ls]], dp[rs][a[rs]]);
}
else if (a[ls] < a[rs]){
dp[i][ai] = mrg(a[ls], dp[ls][ai], dp[rs][a[rs]]);
}
else dp[i][ai] = min(mrg(a[rs], dp[ls][a[ls]], dp[rs][ai]),
mrg(a[rs], dp[ls][ai], dp[rs][a[ls]]));
dp[ls].clear(), dp[rs].clear();
}
}
vec <int> res = dp[1][a[1]];
for (auto &i: res) cout << i << " ";
return 0;
}
inline void precalc(){}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tst = 1; //cin >> tst;
precalc();
while(tst--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
