제출 #714986

#제출 시각아이디문제언어결과실행 시간메모리
714986StickfishSwap (BOI16_swap)C++17
21 / 100
2 ms792 KiB
#include <iostream> #include <vector> using namespace std; const int MAXN = 100; vector<int> dp[MAXN][MAXN]; vector<int> subtr[MAXN]; vector<int> unite_subtr(vector<int> ltr, vector<int> rtr) { auto lit = ltr.begin(); auto rit = rtr.begin(); vector<int> ans = {-1}; for (int sz = 1; lit < ltr.end() || rit < rtr.end(); sz *= 2) { for (int i = 0; i < sz && lit + i < ltr.end(); ++i) ans.push_back(lit[i]); for (int i = 0; i < sz && rit + i < rtr.end(); ++i) ans.push_back(rit[i]); lit += sz; rit += sz; } return ans; } signed main() { int n; cin >> n; vector<int> p(n); for (int i = 0; i < n; ++i) { cin >> p[i]; --p[i]; } for (int i = n - 1; i >= 0; --i) { if (i * 2 + 1 >= n) { for (int t = 0; t < n; ++t) dp[i][t] = {t}; continue; } if (i * 2 + 2 >= n) { for (int t = 0; t < n; ++t) { dp[i][t] = {min(t, p[i * 2 + 1]), max(t, p[i * 2 + 1])}; } continue; } for (int t = 0; t < n; ++t) { int lchd = i * 2 + 1; int rchd = i * 2 + 2; if (t < p[lchd] && t < p[rchd]) { dp[i][t] = unite_subtr(dp[lchd][p[lchd]], dp[rchd][p[rchd]]); dp[i][t][0] = t; continue; } if (p[lchd] < t && p[lchd] < p[rchd]) { dp[i][t] = unite_subtr(dp[lchd][t], dp[rchd][p[rchd]]); dp[i][t][0] = p[lchd]; continue; } // p[rchd] < t, p[lchd] vector<int> dp0 = unite_subtr(dp[lchd][p[lchd]], dp[rchd][t]); vector<int> dp1 = unite_subtr(dp[lchd][t], dp[rchd][p[lchd]]); dp[i][t] = min(dp0, dp1); dp[i][t][0] = p[rchd]; } } for (auto x : dp[0][p[0]]) { cout << x + 1 << ' '; } cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...