Submission #1002569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002569		MilosMilutinovic	Swap (BOI16_swap)	C++14	100 / 100	789 ms	206712 KiB

swap

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    --a[i];
  }
  vector<int> dep(n);
  for (int i = 1; i < n; i++) {
    dep[i] = dep[(i - 1) / 2] + 1;
  }
  vector<vector<int>> all(n);
  for (int i = 0; i < n; i++) {
    all[dep[i]].push_back(i);
  }
  vector<vector<int>> vals(n);
  function<void(int, int)> Update = [&](int i, int v) {
    int L = i * 2 + 1, R = i * 2 + 2;
    if (L >= n) {
      return;
    }
    if (R >= n) {
      if (v < a[L]) {
        vals[L].push_back(a[L]);
      } else {
        vals[L].push_back(v);
      }
      return;
    }
    if (v <= a[L] && v <= a[R]) {
      vals[L].push_back(a[L]);
      vals[R].push_back(a[R]);
    } else if (a[L] <= v && a[L] <= a[R]) {
      vals[L].push_back(v);
      vals[R].push_back(a[R]);
    } else {
      vals[L].push_back(a[L]);
      vals[R].push_back(v);
      vals[L].push_back(v);
      vals[R].push_back(a[L]);
    }
  };
  vals[0].push_back(a[0]);
  for (int d = 0; d < n; d++) {
    for (int i : all[d]) {
      sort(vals[i].begin(), vals[i].end());
      vals[i].erase(unique(vals[i].begin(), vals[i].end()), vals[i].end());
      for (int v : vals[i]) {
        Update(i, v);
      }
    }
  }
  vector<int> sz(n);
  for (int i = 0; i < n; i++) {
    sz[i] = (int) vals[i].size();
  }
  vector<vector<vector<int>>> dp(n);
  for (int i = 0; i < n; i++) {
    dp[i].resize(sz[i]);
  }
  auto Merge = [&](int x, vector<int> va, vector<int> vb) {
    vector<int> v(1, x);
    int pa = 0, pb = 0;
    for (int pw = 1; pa < (int) va.size(); pw *= 2) {
      for (int iter = 0; iter < pw; iter++) {
        if (pa < (int) va.size()) {
          v.push_back(va[pa]);
          pa += 1;
        } else {
          break;
        }
      }
      for (int iter = 0; iter < pw; iter++) {
        if (pb < (int) vb.size()) {
          v.push_back(vb[pb]);
          pb += 1;
        } else {
          break;
        }
      }
    }
    return v;
  };
  function<vector<int>(int, int)> Solve = [&](int i, int v) {
    if (i >= n) {
      return vector<int>{};
    }
    int p = (int) (lower_bound(vals[i].begin(), vals[i].end(), v) - vals[i].begin());
    if (!dp[i][p].empty()) {
      return dp[i][p];
    }
    int L = i * 2 + 1, R = i * 2 + 2;
    if (L >= n) {
      return dp[i][p] = {v};
    }
    if (R >= n) {
      if (v < a[L]) {
        dp[i][p] = Merge(v, Solve(L, a[L]), {});
      } else {
        dp[i][p] = Merge(a[L], Solve(L, v), {});
      }
      return dp[i][p];
    }
    if (v <= a[L] && v <= a[R]) {
      dp[i][p] = Merge(v, Solve(L, a[L]), Solve(R, a[R]));
    } else if (a[L] <= v && a[L] <= a[R]) {
      dp[i][p] = Merge(a[L], Solve(L, v), Solve(R, a[R]));
    } else {
      dp[i][p] = min(Merge(a[R], Solve(L, a[L]), Solve(R, v)), Merge(a[R], Solve(L, v), Solve(R, a[L])));
    }
    return dp[i][p];
  };
  for (int d = n - 1; d >= 0; d--) {
    for (int i : all[d]) {
      for (int v : vals[i]) {
        Solve(i, v);
      }
    }
    if (d + 1 < n) {
      for (int i : all[d + 1]) {
        for (int j = 0; j < sz[i]; j++) {
          vector<int>().swap(dp[i][j]);
        }
      }
    }  
  }
  vector<int> res;
  for (int i = 0; i < (int) vals[0].size(); i++) {
    if (vals[0][i] == a[0]) {
      res = dp[0][i];
    }
  }
  for (int i = 0; i < (int) res.size(); i++) {
    cout << res[i] + 1 << " ";
  }
  cout << '\n';
  return 0;
}

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