Submission #702044

#	Time	Username	Problem	Language	Result	Execution time	Memory
702044		bebra	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	78 ms	16528 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define dbg(x) cerr << #x << ": " << x << endl;


struct FenwickTree {
    vector<int> tree;
    int size;

    FenwickTree(int n) {
        size = n;
        tree.resize(size);
    }

    void update(int pos, int value) {
        for (int i = pos; i < size; i |= i + 1) {
            tree[i] += value;
        }
    }

    int query(int l, int r) {
        int res = 0;
        for (int i = r; i >= 0; i = (i & (i + 1)) - 1) {
            res += tree[i];
        }
        for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) {
            res -= tree[i];
        }
        return res;
    }
};


ll count_swaps(vector<int> a) {
    int n = a.size() / 2;
    vector<vector<int>> left_elms(n + 1), right_elms(n + 1);
    for (int i = 0; i < n * 2; ++i) {
        int x = a[i];
        if (x < 0) {
            left_elms[-x].push_back(i);
        } else {
            right_elms[x].push_back(i);
        }
    }
    vector<pair<int, int>> pairs;
    ll res = 0;
    for (int x = 1; x <= n; ++x) {
        for (int i = 0; i < (int)left_elms[x].size(); ++i) {
            int l = left_elms[x][i];
            int r = right_elms[x][i];
            if (l > r) {
                swap(l, r);
                ++res;
            }
            pairs.emplace_back(l, r);
        }
    }
    sort(pairs.begin(), pairs.end());
    vector<int> p(n * 2);
    for (int i = 0; i < n; ++i) {
        auto [l, r] = pairs[i];
        p[l] = 2 * i;
        p[r] = 2 * i + 1;
    }
    FenwickTree tree(n * 2);
    for (auto x : p) {
        res += tree.query(x + 1, n * 2 - 1);
        tree.update(x, 1);
    }
    return res;
}

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