Submission #591090

#	Time	Username	Problem	Language	Result	Execution time	Memory
591090		dryeab	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	81 ms	14872 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

struct segment_tree {

    int n;
    vector<int> tree;

    void init(int i) {
        n = 1;
        while (n < i)
            n *= 2;
        tree.resize(2 * n, 0);
    }

    void set(int i) {
        i += n;
        tree[i] = 1;
        for (i /= 2; i > 0; i /= 2)
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    int get(int l, int r) {
        l += n;
        r += n;
        int res = 0;
        while (l <= r) {
            if (l & 1)
                res += tree[l++];
            if (!(r & 1))
                res += tree[r--];
            r /= 2, l /= 2;
        }
        return res;
    }
};

long long count_swaps(vector<int> s) {

    int n = s.size(), shift = 0;

    vector<vector<int>> left(n / 2 + 1), right(n / 2 + 1);
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] < 0)
            left[-s[i]].push_back(i);
        else
            right[s[i]].push_back(i);
    }

    long long res = 0;

    segment_tree st;
    st.init(n);

    for (int i = 0, j; i < n; ++i) {

        if (s[i] == 0) {
            // shift--;
            continue;

        } else if (s[i] > 0) {

            j = left[s[i]][left[s[i]].size() - 1];
            left[s[i]].pop_back();
            right[s[i]].pop_back();

            shift = st.get(i + 1, j - 1);
            res += j - i - shift;
            s[j] = s[i] = 0;

            st.set(i), st.set(j);
        } else {

            j = right[-s[i]][right[-s[i]].size() - 1];
            right[-s[i]].pop_back();
            left[-s[i]].pop_back();

            shift = st.get(i + 1, j - 1);

            res += j - i - shift - 1;

            s[j] = s[i] = 0;
            st.set(i), st.set(j);
        }

        // shift++;
    }

    return res;
}

// int main() {

//     ios::sync_with_stdio(false);
//     cin.tie(0);

//     int n;
//     cin >> n;

//     vector<int> s(n);
//     for (int &i : s)
//         cin >> i;

//     cout << "ans " << count_swaps(s) << endl;
// }

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