제출 #242684

#제출 시각아이디문제언어결과실행 시간메모리
242684luciocfSwap (BOI16_swap)C++14
48 / 100
1084 ms262148 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5+10; const int maxl = 35; int a[maxn]; int pai[maxn]; int l[maxn], r[maxn]; vector<int> dp[maxn][maxl]; map<int, int> anc[maxn]; void get_anc(int u) { int ind = 0, v = u; while (v) { anc[u][a[v]] = ++ind; if (l[pai[v]] != v && l[pai[v]]) anc[u][a[l[pai[v]]]] = ++ind; v = pai[v]; } } bool menor(vector<int> a, vector<int> b) { if (!b.size()) return true; for (int i = 0; i < a.size(); i++) { if (a[i] < b[i]) return true; if (a[i] > b[i]) return false; } return true; } vector<int> get(int u, int v, int f1, int x1, int f2, int x2) { vector<int> aux; aux.push_back(v); int ptr = 0; int ind1 = anc[f1][x1], ind2 = anc[f2][x2]; for (int p = 0; ptr + (1<<p)-1 < dp[f2][ind2].size(); p++) { for (int i = ptr; i < ptr + (1<<p); i++) aux.push_back(dp[f1][ind1][i]); for (int i = ptr; i < ptr + (1<<p); i++) aux.push_back(dp[f2][ind2][i]); ptr += (1<<p); } for (int i = ptr; i < dp[f1][ind1].size(); i++) aux.push_back(dp[f1][ind1][i]); for (int i = ptr; i < dp[f2][ind2].size(); i++) aux.push_back(dp[f2][ind2][i]); return aux; } void solve(int u, int v) { if (!u || dp[u][anc[u][v]].size()) return; vector<int> ans; int f1 = l[u], f2 = r[u]; int x1 = a[f1], x2 = a[f2]; solve(f1, x1); solve(f2, x2); vector<int> aux = get(u, v, f1, x1, f2, x2); if (menor(aux, ans)) ans = aux; if (l[u] && r[u]) { x1 = v, x2 = a[l[u]]; solve(f1, x1); solve(f2, x2); aux = get(u, a[r[u]], f1, x1, f2, x2); if (menor(aux, ans)) ans = aux; } if (l[u]) { x1 = v, x2 = a[r[u]]; solve(f1, x1); solve(f2, x2); aux = get(u, a[l[u]], f1, x1, f2, x2); if (menor(aux, ans)) ans = aux; } if (r[u]) { x1 = a[l[u]], x2 = v; solve(f1, x1); solve(f2, x2); aux = get(u, a[r[u]], f1, x1, f2, x2); if (menor(aux, ans)) ans = aux; } dp[u][anc[u][v]] = ans; } int main(void) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { if (2*i <= n) l[i] = 2*i; if (2*i+1 <= n) r[i] = 2*i+1; pai[i] = i/2; } for (int i = 1; i <= n; i++) get_anc(i); solve(1, a[1]); for (auto x: dp[1][anc[1][a[1]]]) printf("%d ", x); printf("\n"); }

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'bool menor(std::vector<int>, std::vector<int>)':
swap.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~
swap.cpp: In function 'std::vector<int> get(int, int, int, int, int, int)':
swap.cpp:52:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int p = 0; ptr + (1<<p)-1 < dp[f2][ind2].size(); p++)
                  ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = ptr; i < dp[f1][ind1].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = ptr; i < dp[f2][ind2].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
#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...