답안 #1002422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002422	2024-06-19T14:43:03 Z	MilosMilutinovic	Swap (BOI16_swap)	C++14	48 / 100	108 ms	262144 KB

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<vector<vector<int>>> dp(n, vector<vector<int>>(n));
  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>{};
    }
    if (!dp[i][v].empty()) {
      return dp[i][v];
    }
    int L = i * 2 + 1, R = i * 2 + 2;
    if (L >= n) {
      return dp[i][v] = {v};
    }
    if (R >= n) {
      return dp[i][v] = min(Merge(v, Solve(L, a[L]), {}), 
                            Merge(a[L], Solve(L, v), {}));
    }
    return dp[i][v] = min({Merge(v, Solve(L, a[L]), Solve(R, a[R])), 
                           Merge(a[L], Solve(L, v), Solve(R, a[R])),
                           Merge(a[R], Solve(L, a[L]), Solve(R, v)),
                           Merge(a[R], Solve(L, v), Solve(R, a[L]))});
  };
  vector<int> res = Solve(0, a[0]);
  for (int i = 0; i < (int) res.size(); i++) {
    cout << res[i] + 1 << " ";
  }
  cout << '\n';
  return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	456 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	360 KB	Output is correct

Subtask #2

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	456 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	360 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	456 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	360 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	16 ms	24408 KB	Output is correct
12	Correct	15 ms	24412 KB	Output is correct
13	Correct	26 ms	24544 KB	Output is correct
14	Correct	14 ms	24408 KB	Output is correct
15	Correct	15 ms	24516 KB	Output is correct

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	456 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	360 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	16 ms	24408 KB	Output is correct
12	Correct	15 ms	24412 KB	Output is correct
13	Correct	26 ms	24544 KB	Output is correct
14	Correct	14 ms	24408 KB	Output is correct
15	Correct	15 ms	24516 KB	Output is correct
16	Runtime error	108 ms	262144 KB	Execution killed with signal 9
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	456 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	360 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	16 ms	24408 KB	Output is correct
12	Correct	15 ms	24412 KB	Output is correct
13	Correct	26 ms	24544 KB	Output is correct
14	Correct	14 ms	24408 KB	Output is correct
15	Correct	15 ms	24516 KB	Output is correct
16	Runtime error	108 ms	262144 KB	Execution killed with signal 9
17	Halted	0 ms	0 KB	-