Submission #1124536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124536		njoop	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	0 ms	324 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) {
    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(*st.find_by_order(i) != 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);
        st.erase(st.find_by_order(idx));
        st.erase(st.find_by_order(i));
        if(s[i] > 0) ans++;
    }
    return ans;
}

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