Submission #1066232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066232		arbuzick	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	103 ms	140680 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>

using namespace std;

struct Fenwick {
    int n;
    vector<int> f;

    Fenwick(int _n) {
        n = _n;
        f.assign(n, 0);
    }

    void add(int pos, int val) {
        for (int i = pos; i < n; i += i & -i) {
            f[i] += val;
        }
    }

    int get(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= i & -i) {
            ans += f[i];
        }
        return ans;
    }
};

long long count_inv(vector<int> ord) {
    int len = ord.size();
    Fenwick f(len + 1);
    long long ans = 0;
    for (auto vl : ord) {
        ans += f.get(len) - f.get(vl);
        f.add(vl, 1);
    }
    return ans;
}

long long count_swaps(vector<int> s) {
    int n = s.size() / 2;
    vector<int> ord_nw(n * 2);
    int pos_l = 1;
    vector<queue<int>> q_l(n + 1), q_r(n + 1);
    for (int i = 0; i < n * 2; ++i) {
        if (s[i] < 0) {
            if (!q_r[-s[i]].empty()) {
                ord_nw[i] = q_r[-s[i]].front();
                q_r[-s[i]].pop();
            } else {
                ord_nw[i] = pos_l;
                q_l[-s[i]].push(pos_l + 1);
                pos_l += 2;
            }
        } else {
            if (!q_l[s[i]].empty()) {
                ord_nw[i] = q_l[s[i]].front();
                q_l[s[i]].pop();
            } else {
                ord_nw[i] = pos_l + 1;
                q_r[s[i]].push(pos_l);
                pos_l += 2;
            }
        }
    }
    return count_inv(ord_nw);
}

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