Submission #877357

#	Time	Username	Problem	Language	Result	Execution time	Memory
877357		mychecksedad	Swap (BOI16_swap)	C++17	0 / 100	57 ms	195924 KiB

swap

/* 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<<4), 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 (stderr)

swap.cpp: In function 'int main()':
swap.cpp:120:15: warning: unused variable 'aa' [-Wunused-variable]
  120 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32