Submission #1136250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136250		Hamed_Ghaffari	Swap (BOI16_swap)	C++20	100 / 100	706 ms	219204 KiB

swap

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

#define pb push_back
#define all(x) x.begin(), x.end()

const int MXN = 2e5+1;

struct node {
  int val;
  node *lc, *rc;
  node(int val=0, node *lc=NULL, node *rc=NULL): val(val), lc(lc), rc(rc) {}
};

int n, a[MXN];
vector<int> vals[MXN];
vector<node*> dp[MXN];

void dfs(int v) {
  vals[v].pb(a[v]);
  dp[v].resize(vals[v].size(), NULL);
  if((v<<1)<=n) {
    vals[v<<1] = vals[v];
    if((v<<1|1)<=n) vals[v<<1].pb(a[v<<1|1]);
    dfs(v<<1);
  }
  if((v<<1|1)<=n) {
    vals[v<<1|1] = vals[v];
    vals[v<<1|1].pb(a[v<<1]);
    dfs(v<<1|1);
  }
}

inline vector<node*> arr(node *v) {
  vector<node*> q;
  q.pb(v);
  int ptr=0;
  while(ptr<q.size()) {
    v = q[ptr++];
    if(v->lc) q.pb(v->lc);
    if(v->rc) q.pb(v->rc);
  }
  return q;
}

bool operator<(vector<node*> &A, vector<node*> &B) {
  for(int i=0; i<A.size(); i++)
    if(A[i]->val<B[i]->val) return 1;
    else if(A[i]->val>B[i]->val) return 0;
}

node *DP(int v, int x) {
  int p = lower_bound(all(vals[v]), x)-vals[v].begin();
  if(dp[v][p]) return dp[v][p];
  if((v<<1)>n) return dp[v][p] = new node(x);
  if((v<<1|1)>n) {
    if(x<a[v<<1]) return dp[v][p] = new node(x, DP(v<<1, a[v<<1]));
    else return dp[v][p] = new node(a[v<<1], DP(v<<1, x));
  }
  if(x<a[v<<1] && x<a[v<<1|1])
    return dp[v][p] = new node(x, DP(v<<1, a[v<<1]), DP(v<<1|1, a[v<<1|1]));
  if(a[v<<1] < a[v<<1|1])
    return dp[v][p] = new node(a[v<<1], DP(v<<1, x), DP(v<<1|1, a[v<<1|1]));
  dp[v][p] = new node(a[v<<1|1], DP(v<<1, x), DP(v<<1|1, a[v<<1]));
  vector<node*> v1 = arr(dp[v][p]);
  dp[v][p]->lc = DP(v<<1, a[v<<1]); dp[v][p]->rc = DP(v<<1|1, x);
  vector<node*> v2 = arr(dp[v][p]);
  if(v1<v2) dp[v][p]->lc = DP(v<<1, x), dp[v][p]->rc = DP(v<<1|1, a[v<<1]);
  return dp[v][p];
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n;
  for(int i=1; i<=n; i++) cin >> a[i];
  dfs(1);
  for(int i=1; i<=n; i++)
    sort(all(vals[i]));
  vector<node*> ans = arr(DP(1, a[1]));
  for(node *v : ans) cout << v->val << ' ';
  cout << '\n';
  return 0;
}

Compilation message (stderr)

swap.cpp: In function 'bool operator<(std::vector<node*>&, std::vector<node*>&)':
swap.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

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