Submission #699943

#	Time	Username	Problem	Language	Result	Execution time	Memory
699943		elkernos	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	309 ms	407116 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"

using namespace std;

#define ssize(x) (int)size(x)
template <class A, class B>
auto &operator<<(ostream &o, pair<A, B> p)
{
    return o << '(' << p.first << ", " << p.second << ')';
}
template <class T>
auto operator<<(ostream &o, T x) -> decltype(x.end(), o)
{
    o << '{';
    int i = 0;
    for (auto e : x)
        o << (", ") + 2 * !i++ << e;
    return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) \
    {              \
    }
#endif

long long count_swaps(vector<int> s)
{
    int n = ssize(s);
    vector<vector<deque<int>>> pos(2, vector<deque<int>>(n + 1));
    vector<int> pary(n);
    vector<int> order;
    for (int i = 0; i < n; i++) {
        int rozm = abs(s[i]), sign = s[i] > 0;
        if (ssize(pos[sign ^ 1][rozm])) {
            int kto = pos[sign ^ 1][rozm].front();
            pos[sign ^ 1][rozm].pop_front();
            pary[kto] = i;
        }
        else {
            pos[sign][rozm].push_back(i);
            order.push_back(i);
        }
    }
    debug(pary, order);
    vector<int> fen(n + 1);
    auto pisz = [&](int x) {
        for (x++; x; x -= x & -x)
            fen[x]++;
    };
    auto ile = [&](int x) {
        int ans = 0;
        for (x++; x <= n; x += x & -x)
            ans += fen[x];
        return ans;
    };
    long long ans = 0;
    for (int x : order) {
        int lo = x + ile(x);
        int hi = pary[x] + ile(pary[x]);
        ans += hi - lo - 1 + (s[x] > 0);
        debug(ans);
        pisz(pary[x]);
    }
    return ans;
}

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