| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 877371 |
2023-11-23T07:56:02 Z |
mychecksedad |
Swap (BOI16_swap) |
C++17 |
|
47 ms |
197716 KB |
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = (1<<10), K = 52, MX = 30;
int n, a[N];
map<int, array<int, 3>> dp[N][4];
array<int, 3> f(array<int, 3> x, array<int, 3> y){
return min(x, y);
}
void dfs(int v){
if(v >= M){
return;
}
// cout << v << endl;
dfs(v<<1);
dfs(v<<1|1);
vector<int> states;
// if((v<<1) <= M)
// states.pb(a[v<<1]);
// if((v<<1|1) <= M)
// states.pb(a[v<<1|1]);
for(int u = v; u >= 1; u >>= 1){
states.pb(a[u]);
if((u&1) && u > 1) states.pb(a[u^1]);
}
for(int &top: states){
// cout << top << ' ' << v << '\n';
for(int l = 0; l < 4; ++l){
if((v<<1) >= M / 2){
// if(v==4) cout << l << ' ' << top << '\n';
if(l == 0) dp[v][l][top] = {top, MOD, MOD};
else dp[v][l][top] = {MOD, MOD, MOD};
continue;
}
array<int, 3> DP = {MOD, MOD, MOD};
int ax, ay, az;
if(l == 0) ax = top, ay = a[v<<1], az = a[v<<1|1];
else if(l == 1) ax = a[v<<1], ay = top, az = a[v<<1|1];
else if(l == 2) ax = a[v<<1|1], ay = top, az = a[v<<1];
else ax = a[v<<1|1], ay = a[v<<1], az = top;
for(int i = 0; i < 4; ++i){
for(int j = 0; j < 4; ++j){
auto L = dp[v<<1][i][ay][0];
auto R = dp[v<<1|1][j][az][0];
if(L == 0) L = MOD;
if(R == 0) R = MOD;
DP = min(DP, array<int, 3>{ax, L, R});
}
}
dp[v][l][top] = DP;
}
}
}
void solve(){
cin >> n;
for(int i = 1; i <= n ;++i) cin >> a[i];
for(int j = n + 1; j < N; ++j) a[j] = MOD;
dfs(1);
// for(int i = 1; i <= 5; ++i){
// for(int j = 0; j < 4; ++j){
// for(auto st: dp[i][j]){
// cout << i << ' ' << j << ' ' << st.first << ':' << st.second[0] << ' ' << st.second[1] << ' ' << st.second[2] << '\n';
// }
// en;
// }
// en;
// }
vector<int> ans;
vector<int> besttop(N);
besttop[1] = a[1];
for(int v = 1; v <= n; ++v){
int top = besttop[v];
vector<pair<array<int, 3>, int>> dps;
for(int l = 0; l < 4; ++l){
dps.pb({dp[v][l][top], l});
}
sort(all(dps));
auto DP = dps[0].first;
int l = dps[0].second;
ans.pb(DP[0]);
if(l == 0){
besttop[v<<1] = a[v<<1];
besttop[v<<1|1] = a[v<<1|1];
}else if(l == 1){
besttop[v<<1] = top;
besttop[v<<1|1] = a[v<<1|1];
}else if(l == 2){
besttop[v<<1] = top;
besttop[v<<1|1] = a[v<<1];
}else{
besttop[v<<1] = a[v<<1];
besttop[v<<1|1] = top;
}
}
for(int x: ans) cout << x << ' ';
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:120:15: warning: unused variable 'aa' [-Wunused-variable]
120 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
197716 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
197716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
197716 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
197716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
197716 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
197716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
197716 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
197716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
197716 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
197716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
