Submission #724075

#	Time	Username	Problem	Language	Result	Execution time	Memory
724075		_martynas	Swap (BOI16_swap)	C++14	100 / 100	167 ms	33388 KiB

swap

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define PB push_back

struct Decision {
    Decision *def = nullptr, *oth = nullptr; // default, other
    bool locked = false; // locked state is shared between swappable pairs
    int val = 0; // leaf nodes aren't actual decisions and have >0 values
    Decision *link = nullptr; // linked decision
    Decision() {};
    Decision(int x) {
        // leaf node constructor
        val = x;
    }
    Decision(Decision* _def, Decision* _oth) {
        def = _def, oth = _oth;
    }
    int get() {
        if(val) return (locked ? 1e8 : val);
        if(locked) return def->get(); // other is not an option
        return min(def->get(), oth->get());
    }
    bool rem(int x) {
        // lock all decisions that lead to the one at the top of the stack
        // get()'ing x
        if(val == x) {
            locked = true;
            return true;
        }
        if(val) return false;
        bool found = def->rem(x);
        if(found) {
            locked = true;
            return true;
        }
        found = oth->rem(x);
        if(found) {
            locked = true;
            swap(def, oth);
            link->locked = true;
            swap(link->def, link->oth);
            return true;
        }
        return false;
    }
};

const int MXN = 200'005;

int n, A[MXN];
Decision* D[MXN];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> A[i];
    for(int i = 1; i <= n; i++) {
        D[i] = new Decision(A[i]);
    }
    for(int i = 2; i <= n; i++) {
        int j = i/2;
        tie(D[j], D[i]) = make_tuple(new Decision(D[j], D[i]), new Decision(D[i], D[j]));
        D[j]->link = D[i], D[i]->link = D[j];
    }
    for(int i = 1; i <= n; i++) {
        int x = D[i]->get();
        D[i]->rem(x);
        cout << x << " \n"[i == n];
    }
    return 0;
}

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