Submission #1124544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124544		njoop	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	564 ms	33316 KiB

shoes

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;

ordered_multiset st;
map<int, vector<int>> mp;

bool cmp(int &a, int &b) {
    return a > b;
}

long long count_swaps(vector<int> s) {
    vector<bool> isSel;
    isSel.assign(s.size()+10, 0);
    st.clear();
    mp.clear();
    long long ans = 0;
    for(int i=0; i<s.size(); i++) {
        st.insert(i); 
        mp[s[i]].push_back(i);
    }
    for(auto &i: mp) {
        sort(i.second.begin(), i.second.end(), cmp);
    }
    for(int i=0; i<s.size(); i++) {
        if(isSel[i]) continue;
        int idx = mp[-s[i]].back();
        mp[-s[i]].pop_back();
        mp[s[i]].pop_back();
        ans += st.order_of_key(idx)-st.order_of_key(i)-1;
        st.erase(st.find_by_order(st.order_of_key(idx)));
        st.erase(st.find_by_order(st.order_of_key(i)));
        isSel[i] = 1;
        isSel[idx] = 1;
        if(s[i] > 0) ans++;
    }
    return ans;
}

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