Submission #486833

#	Time	Username	Problem	Language	Result	Execution time	Memory
486833		Haidara	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	261 ms	31480 KiB

shoes

    #include <map>
    #include <ext/pb_ds/assoc_container.hpp>
    #include "shoes.h"
     
    using namespace std;
    using namespace __gnu_pbds;
     
    template<typename T, typename Tk>
    using os_map = tree<
        T, Tk, less<T>, rb_tree_tag, tree_order_statistics_node_update
    >;
    template<typename T>
    using os_set = os_map<T, null_type>;
     
    long long count_swaps(vector<int> S)
    {
        const size_t n = S.size();
     
        vector<vector<size_t>> pos(2*n);
        for(size_t i = n; i --> 0; )
            pos[S[i] + n].push_back(i);
     
        os_set<size_t> erased;
        size_t mex = 0;
        long long result = 0;
        while(erased.size() < n)
        {
            while(erased.find(mex) != erased.end())
                mex++;
     
            auto i = pos[-S[mex] + n].back();
     
            result += i - (mex + 1) - (erased.order_of_key(i) - erased.order_of_key(mex));
     
            if(S[mex] > 0)
                result++;
            erased.insert(mex);
            pos[S[mex] + n].pop_back();
            erased.insert(i);
            pos[-S[mex] + n].pop_back();
        }
     
        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