Submission #576108

#	Time	Username	Problem	Language	Result	Execution time	Memory
576108		Do_you_copy	Swap (BOI16_swap)	C++14	100 / 100	87 ms	37176 KiB

swap

#include <bits/stdc++.h>
#define ll long long
#define taskname ""
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

const ll Mod = 1000000007;
const int maxN = 2e5 + 1;
int n;
int a[8 * maxN + 1];

map <int, int> m[maxN];

int get(int id, int val) {
    if (m[id].find(val) != m[id].end())
        return m[id][val];

    if (val < a[id * 2] && val < a[id * 2 + 1])
        return m[id][val] = id;

    if (a[id * 2] < val && a[id * 2] < a[id * 2 + 1])
        return m[id][val] = get(id * 2, val);

    int Min = min(val, a[id * 2]);

    if (get(id * 2, Min) < get(id * 2 + 1, Min)) {
        if (val == Min)
            return m[id][val] = get(id * 2, val);

        return m[id][val] = get(id * 2 + 1, val);
    }

    if (val == Min)
        return m[id][val] = get(id * 2 + 1, val);

    return m[id][val] = get(id * 2, val);
}

void Init() {
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = n + 1; i <= 8 * maxN; ++i)
        a[i] = INT_MAX;

    for (int i = 1; i <= n; ++i) {
        if (a[i] < a[i * 2] && a[i] < a[i * 2 + 1])
            continue;

        if (a[i * 2] < a[i] && a[i * 2] < a[i * 2 + 1])
            swap(a[i * 2], a[i]);
        else {
            int Min = min(a[i], a[i * 2]);
            int Max = max(a[i], a[i * 2]);
            swap(a[i * 2 + 1], a[i]);

            if (get(i * 2, Min) < get(i * 2 + 1, Min)) {
                a[i * 2] = Min;
                a[i * 2 + 1] = Max;
            } else {
                a[i * 2] = Max;
                a[i * 2 + 1] = Min;
            }
        }
    }

    for (int i = 1; i <= n; ++i)
        cout << a[i] << " ";
}

int main() {
    faster
    Init();
}

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