oj.uz

Submission #224284

# Submission time Handle Problem Language Result Execution time Memory
224284 2020-04-17T16:17:35 Z Bruteforceman Swap (BOI16_swap) C++11
68 / 100
 1000 ms 216456 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
const int maxn = 2e5 + 5;
unordered_map <int, int> dp[maxn], op[maxn];
int a[maxn];
int n;

void dfs(int x) {
  int l = x << 1;
  int r = l + 1;
  if(l <= n) dfs(l);
  if(r <= n) dfs(r);
  
  vector <int> imp;
  int cur = x;
  imp.emplace_back(a[x]);
  while(cur > 1) {
    int nxt = cur / 2;
    imp.emplace_back(a[nxt]);
    if(cur & 1) imp.emplace_back(a[cur ^ 1]);
    cur = nxt;
  }
  dp[x].reserve(imp.size() + 1);
  op[x].reserve(imp.size() + 1);
  dp[x].max_load_factor(0.25);
  op[x].max_load_factor(0.25);
  if(r <= n) {
    for(int y : imp) { 
      vector <pii> opt ({{INT_MAX, INT_MAX}, {INT_MAX, INT_MAX}, {INT_MAX, INT_MAX}});
      for(int i = 0; i <= 1; i++) {
      for(int j = 0; j <= 1; j++) {
        int p = y, q = a[l], s = a[r];
        if(i) swap(p, q);
        if(j) swap(p, s);
        vector <pii> can;
        can.emplace_back(x, p);
        can.emplace_back(dp[l][q], q);
        can.emplace_back(dp[r][s], s);
        sort(can.begin(), can.end());
        if(opt > can) {
          opt = can;
          for(auto w : can) if(w.second == y) dp[x][y] = w.first;
          op[x][y] = j * 2 + i;
        }
      }
    }
    }
  } else if (l <= n) {
    for(int y : imp) {
      vector <pii> opt ({{INT_MAX, INT_MAX}, {INT_MAX, INT_MAX}});
      for(int i = 0; i <= 1; i++) {
      int p = y, q = a[l];
      if(i) swap(p, q);
      vector <pii> can;
      can.emplace_back(x, p);
      can.emplace_back(dp[l][q], q);
      sort(can.begin(), can.end());
      if(opt > can) {
        opt = can;
        for(auto w : can) if(w.second == y) dp[x][y] = w.first;
        op[x][y] = i;
      }
      }
    }
  } else {
    for(int y : imp) {
      dp[x][y] = x;
      op[x][y] = 0;
    }
  }
  if(l <= n) dp[l].clear();
  if(r <= n) dp[r].clear();
}

void getOpt(int x) {
  int i = op[x][a[x]] & 1;
  int j = op[x][a[x]] >> 1;
  int l = x << 1;
  int r = l + 1;
  if(i) swap(a[x], a[l]);
  if(j) swap(a[x], a[r]);
  if(l <= n) getOpt(l);
  if(r <= n) getOpt(r);
}

int main() {
  ios_base :: sync_with_stdio (false);
  cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  dfs(1);
  getOpt(1);
  for(int i = 1; i <= n; i++) {
    cout << a[i] << ' ';
  }
  cout << endl;
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22272 KB Output is correct
2 Correct 19 ms 22272 KB Output is correct
3 Correct 20 ms 22272 KB Output is correct
4 Correct 19 ms 22272 KB Output is correct
5 Correct 19 ms 22272 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22272 KB Output is correct
2 Correct 19 ms 22272 KB Output is correct
3 Correct 20 ms 22272 KB Output is correct
4 Correct 19 ms 22272 KB Output is correct
5 Correct 19 ms 22272 KB Output is correct
6 Correct 25 ms 22272 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 20 ms 22272 KB Output is correct
9 Correct 19 ms 22272 KB Output is correct
10 Correct 19 ms 22272 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22272 KB Output is correct
2 Correct 19 ms 22272 KB Output is correct
3 Correct 20 ms 22272 KB Output is correct
4 Correct 19 ms 22272 KB Output is correct
5 Correct 19 ms 22272 KB Output is correct
6 Correct 25 ms 22272 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 20 ms 22272 KB Output is correct
9 Correct 19 ms 22272 KB Output is correct
10 Correct 19 ms 22272 KB Output is correct
11 Correct 33 ms 23808 KB Output is correct
12 Correct 30 ms 23808 KB Output is correct
13 Correct 29 ms 23808 KB Output is correct
14 Correct 34 ms 23808 KB Output is correct
15 Correct 36 ms 23936 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22272 KB Output is correct
2 Correct 19 ms 22272 KB Output is correct
3 Correct 20 ms 22272 KB Output is correct
4 Correct 19 ms 22272 KB Output is correct
5 Correct 19 ms 22272 KB Output is correct
6 Correct 25 ms 22272 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 20 ms 22272 KB Output is correct
9 Correct 19 ms 22272 KB Output is correct
10 Correct 19 ms 22272 KB Output is correct
11 Correct 33 ms 23808 KB Output is correct
12 Correct 30 ms 23808 KB Output is correct
13 Correct 29 ms 23808 KB Output is correct
14 Correct 34 ms 23808 KB Output is correct
15 Correct 36 ms 23936 KB Output is correct
16 Correct 835 ms 145272 KB Output is correct
17 Correct 741 ms 145144 KB Output is correct
18 Correct 836 ms 145272 KB Output is correct
19 Correct 817 ms 145272 KB Output is correct
20 Correct 810 ms 145260 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22272 KB Output is correct
2 Correct 19 ms 22272 KB Output is correct
3 Correct 20 ms 22272 KB Output is correct
4 Correct 19 ms 22272 KB Output is correct
5 Correct 19 ms 22272 KB Output is correct
6 Correct 25 ms 22272 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 20 ms 22272 KB Output is correct
9 Correct 19 ms 22272 KB Output is correct
10 Correct 19 ms 22272 KB Output is correct
11 Correct 33 ms 23808 KB Output is correct
12 Correct 30 ms 23808 KB Output is correct
13 Correct 29 ms 23808 KB Output is correct
14 Correct 34 ms 23808 KB Output is correct
15 Correct 36 ms 23936 KB Output is correct
16 Correct 835 ms 145272 KB Output is correct
17 Correct 741 ms 145144 KB Output is correct
18 Correct 836 ms 145272 KB Output is correct
19 Correct 817 ms 145272 KB Output is correct
20 Correct 810 ms 145260 KB Output is correct
21 Execution timed out 1092 ms 216456 KB Time limit exceeded
22 Halted 0 ms 0 KB -