Submission #1138946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138946		Aliyyiakbar	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	445 ms	242264 KiB

shoes

#include "shoes.h"
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/hash_policy.hpp"
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using __indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

long long count_swaps(vector<int> a)
{
    int n = a.size();
    __indexed_set< pair<int, int> > st;
    gp_hash_table<int, queue<int> > mp;
    for (int i = 0; i < n; ++i)
    {
        mp[a[i]].push(i);
        st.insert({i, a[i]});
    }
    long long result = 0;
    while(!st.empty())
    {
        int shoe = st.begin() -> second;
        int shoePair = mp[-shoe].front();
        result = result + 1LL * (st.order_of_key({shoePair, -shoe})) - (shoe < 0LL);
        mp[shoe].pop();
        mp[-shoe].pop();
        st.erase({shoePair, -shoe});
        st.erase(st.begin());
    }
    return result;
}

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