oj.uz

Submission #224175

# Submission time Handle Problem Language Result Execution time Memory
224175 2020-04-17T11:09:13 Z Bruteforceman Swap (BOI16_swap) C++11
0 / 100
 5 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
int dp[1005][1005];
int a[1005];
int op[1005][1005];
int n;

void dfs(int x) {
  int l = x << 1;
  int r = l + 1;
  if(l <= n) dfs(l);
  if(r <= n) dfs(r);
  if(r <= n) {
    for(int y = 1; y <= n; y++) { 
      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 = 1; y <= n; y++) {
      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) dp[x][y] = w.first;
        op[x][y] = i;
      }
    }
    }
  } else {
    for(int y = 1; y <= n; y++) {
      dp[x][y] = x;
    }
  }
}

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() {
  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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -