| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 242668 |
2020-06-28T21:41:24 Z |
luciocf |
Swap (BOI16_swap) |
C++14 |
|
107 ms |
188280 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e5+10;
const int maxl = 38;
int a[maxn];
int pai[maxn];
int l[maxn], r[maxn];
vector<pii> 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<pii> a, vector<pii> b)
{
if (!b.size()) return true;
for (int i = 0; i < a.size(); i++)
{
if (a[i].ff < b[i].ff) return true;
if (a[i].ff > b[i].ff) return false;
}
return false;
}
vector<pii> get(int u, int v, int f1, int x1, int f2, int x2)
{
vector<pii> aux;
aux.push_back({v, u});
int ptr1 = 0, ptr2 = 0;
int ind1 = anc[f1][x1], ind2 = anc[f2][x2];
while (ptr1 < dp[f1][ind1].size() || ptr2 < dp[f2][ind2].size())
{
if (ptr1 == dp[f1][ind1].size())
{
aux.push_back(dp[f2][ind2][ptr2++]);
}
else if (ptr2 == dp[f2][ind2].size())
{
aux.push_back(dp[f1][ind1][ptr1++]);
}
else if (dp[f1][ind1][ptr1].ss < dp[f2][ind2][ptr2].ss)
{
aux.push_back(dp[f1][ind1][ptr1++]);
}
else
{
aux.push_back(dp[f2][ind2][ptr2++]);
}
}
return aux;
}
void solve(int u, int v)
{
if (!u || dp[u][anc[u][v]].size()) return;
vector<pii> ans;
int f1 = l[u], f2 = r[u];
int x1 = a[f1], x2 = a[f2];
solve(f1, x1);
solve(f2, x2);
vector<pii> aux = get(u, v, f1, x1, f2, x2);
if (menor(aux, ans)) ans = aux;
x1 = a[u], x2 = a[l[u]];
solve(f1, x1);
solve(f2, x2);
aux = get(u, a[r[u]], f1, x1, f2, x2);
if (r[u] && menor(aux, ans)) ans = aux;
x1 = a[u], x2 = a[r[u]];
solve(f1, x1);
solve(f2, x2);
aux = get(u, a[l[u]], f1, x1, f2, x2);
if (l[u] && menor(aux, ans)) ans = aux;
x1 = a[l[u]], x2 = a[u];
solve(f1, x1);
solve(f2, x2);
aux = get(u, a[r[u]], f1, x1, f2, x2);
if (r[u] && 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.ff);
printf("\n");
}
Compilation message
swap.cpp: In function 'bool menor(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
swap.cpp:40: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<std::pair<int, int> > get(int, int, int, int, int, int)':
swap.cpp:57:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 < dp[f1][ind1].size() || ptr2 < dp[f2][ind2].size())
~~~~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:57:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 < dp[f1][ind1].size() || ptr2 < dp[f2][ind2].size())
~~~~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:59:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ptr1 == dp[f1][ind1].size())
~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if (ptr2 == dp[f2][ind2].size())
~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
swap.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
188280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
188280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
188280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
188280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
188280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
