제출 #235652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235652		triple_fault	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	7 ms	1920 KiB

shoes

#include "shoes.h"

#include <set>
#include <cstdio>
#include <algorithm>

#define ll long long
#define mid ((tl + tr) / 2)

using namespace std;

ll n;
vector<ll> shoes(200000);

struct segtree {
    segtree* left = NULL; segtree* right = NULL;
    multiset<ll> here;
    ll m_tl, m_tr;

    void build(ll tl, ll tr) {
        m_tl = tl, m_tr = tr;

        if (tl == tr) {
            here.insert(shoes[tl]);
            return;
        }
        left = new segtree();
        right = new segtree();
        left->build(tl, mid);
        right->build(mid + 1, tr);

        merge(left->here.begin(), left->here.end(), right->here.begin(), right->here.end(),
                inserter(here, here.begin()));
    }

    ll query(ll needle) {
        here.erase(here.find(needle));
        if (m_tl == m_tr) return m_tl;

        if (left->here.find(needle) != left->here.end()) 
            return left->query(needle);
        else if (right->here.find(needle) != right->here.end())
            return right->query(needle);
        else puts("fuck this");
        return 696969696969696969;
    }
} segtree;

long long count_swaps(std::vector<int> s) {
    ll n = s.size();
    for (ll i = 0; i < n; ++i) shoes[i] = (ll)s[i];

    segtree.build(0, n - 1);

    ll active[n];
    for (ll i = 0; i < n; ++i) active[i] = 1;

    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        if (!active[i]) continue;
        active[i] = 0;

        segtree.query(shoes[i]);
        ll nxt = -shoes[i];

        ll q = segtree.query(nxt);
        active[q] = 0;
        ans += (q - i - 1);
        if (nxt < 0) ++ans;
    }
	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15