이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |