Submission #235945

#	Time	Username	Problem	Language	Result	Execution time	Memory
235945		triple_fault	Arranging Shoes (IOI19_shoes)	C++14	Compilation error	0 ms	0 KiB

shoes

#include "shoes.h"

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

#define ll long long
#define mid ((tl + tr) / 2)
#define lft (v * 2)
#define rht ((v * 2) + 1)
#define MAX 200000

using namespace std;

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

struct segtree {
    segtree* left = NULL; segtree* right = NULL;
    multiset<ll> here;
    ll m_tl, m_tr;
    bool inactive = true;
    ll sum_here = 0;

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

        if (tl == tr) {
            here.insert(shoes[tl]);
            inactive = false;
            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));
        ++sum_here;
        if (m_tl == m_tr) {
            inactive = true;
            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 MAX * MAX;
    }

    ll sum(ll tl, ll tr) {
        if (tl > tr) return 0;
        if (tl == m_tl && tr == m_tr) return sum_here;

        return left->sum(tl, min(tr, (m_tl + m_tr) / 2)) +
            right->sum(max(tl, ((m_tl + m_tr) / 2) + 1), tr);
    }

} 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 inactive_a[n];
    memset(inactive_a, 0, sizeof inactive_a);

    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        if (inactive_a[i]) continue;
        segtree.query(shoes[i]);
        ll nxt = -shoes[i];

        ll q = segtree.query(nxt);
        ans += (q - i - 1 - segtree.sum(i + 1, q - 1)); 
        if (nxt < 0) ++ans;

        inactive_a[i] = 1; inactive_a[q] = 1;
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'long long int segtree::query(long long int)':
shoes.cpp:55:20: warning: integer overflow in expression [-Woverflow]
         return MAX * MAX;
                    ^
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:75:5: error: 'memset' was not declared in this scope
     memset(inactive_a, 0, sizeof inactive_a);
     ^~~~~~
shoes.cpp:75:5: note: suggested alternative: 'fd_set'
     memset(inactive_a, 0, sizeof inactive_a);
     ^~~~~~
     fd_set