Submission #672497

#	Time	Username	Problem	Language	Result	Execution time	Memory
672497		tamthegod	Swap (BOI16_swap)	C++14	100 / 100	84 ms	31720 KiB

swap

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 10;
 
int n, a[N];
map <int, int> f[N];
 
int GetPos(int u, int val) {
    if (f[u].find(val) != f[u].end()) return f[u][val];
    if (u * 2 > n) return f[u][val] = u;
    if (val < a[u * 2] && val < a[u * 2 + 1]) return f[u][val] = u;
    if (a[u * 2] < val && a[u * 2] < a[u * 2 + 1]) return f[u][val] = GetPos(u * 2, val);
    else {
        int Min = min(val, a[u * 2]);
        int Max = max(val, a[u * 2]);
        if (GetPos(u * 2, Min) < GetPos(u * 2 + 1, Min)) {
            if (val == Min) return f[u][val] = GetPos(u * 2, val);
            else return f[u][val] = GetPos(u * 2 + 1, val);
        } else {
            if (val == Min) return f[u][val] = GetPos(u * 2 + 1, val);
            else return f[u][val] = GetPos(u * 2, val);
        }
    }
//    assert(0);
}
 
int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    memset(a, 60, sizeof(a));
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int u = 1; u <= n; ++u) {
        if (u * 2 > n) continue;
        if (a[u] < a[u * 2] && a[u] < a[u * 2 + 1]) continue;
        if (a[u * 2] < a[u] && a[u * 2] < a[u * 2 + 1])
            swap(a[u * 2], a[u]);
        else {
            int Min = min(a[u], a[u * 2]);
            int Max = max(a[u], a[u * 2]);
            swap(a[u * 2 + 1], a[u]);
            if (GetPos(u * 2, Min) < GetPos(u * 2 + 1, Min)) {
                a[u * 2] = Min;
                a[u * 2 + 1] = Max;
            } else {
                a[u * 2] = Max;
                a[u * 2 + 1] = Min;
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
}

Compilation message (stderr)

swap.cpp: In function 'int GetPos(int, int)':
swap.cpp:17:13: warning: unused variable 'Max' [-Wunused-variable]
   17 |         int Max = max(val, a[u * 2]);
      |             ^~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32