Submission #289954

#	Time	Username	Problem	Language	Result	Execution time	Memory
289954		mth1908	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	110 ms	11504 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define ar array
#define pii pair<int, int>
#define sz(s) (int) s.size()
#define all(s) s.begin(), s.end()

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int N = 2e5 + 5;

struct BIT {
    int t[N];

    void upd(int x, int v) {
        for (int i = x; i < N; i += i & (-i)) t[i] += v;
    }

    int qry(int x) {
        int ret = 0;
        for (int i = x; i > 0; i -= i & (-i)) ret += t[i];
        return ret;
    }
} bit;

vector<pii> ord[N];

ll count_swaps(std::vector<int> s) {
    int n = sz(s) / 2;
    ll ret = 0;
    vector<pii> v;
    for (int i = 0; i < sz(s); i++) {
        ord[abs(s[i])].emplace_back(s[i], i);
    }
    for (int i = 1; i <= n; i++) {
        sort(all(ord[i]));
        for (int j = 0; j < sz(ord[i]) / 2; j++) {
            int l = ord[i][j].second;
            int r = ord[i][j + sz(ord[i]) / 2].second;
            if (l > r) {
                swap(l, r);
                ret++;
            }
            v.emplace_back(l + 1, r + 1);
        }
    }
    for (int i = 1; i <= 2 * n; i++) bit.upd(i, 1);
    sort(all(v));
    for (auto i : v) {
        ret += bit.qry(i.second - 1) - bit.qry(i.first);
        bit.upd(i.first, -1);
        bit.upd(i.second, -1);
    }
    return ret;
}

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