Submission #911351

#	Time	Username	Problem	Language	Result	Execution time	Memory
911351		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	695 ms	44196 KiB

shoes

    #include "shoes.h"
    #include <bits/stdc++.h>
    using namespace std;
    using ll = long long;
    #define F(i, l, r) for (ll i = l; i < (r); ++i)
    using vl = vector<ll>;
    #define A(a) (a).begin(), (a).end()
     
     
    //GCC extensions
    #include <bits/extc++.h>
    using namespace __gnu_cxx;
    using namespace __gnu_pbds;
     
    // order stats tree
    // find_by_order(i) returns ptr
    // order_of_key(key) return int
    typedef tree<ll, null_type, less<ll>,
    rb_tree_tag, tree_order_statistics_node_update> set_t;
     
    long long count_swaps(std::vector<int> s) {
        ll n = s.size()/2;
     
        map<ll, set<ll>> positions;
        set_t active_nodes;
        for(int i=0;i<s.size();i++) {
            positions[s[i]].insert(i);
            active_nodes.insert(i);
        }
        ll ans = 0;
        
        for(int i=0;i<n;i++) {
            auto si = *active_nodes.begin();
            auto iterator = positions[-s[si]].begin();
            positions[s[si]].erase(si);
            positions[-s[si]].erase(iterator);
            auto it = *iterator;
            
            if (s[si] < 0) {
                ans += active_nodes.order_of_key(it) - 1;
            } else {
                ans += active_nodes.order_of_key(it) ;
            }
            active_nodes.erase(active_nodes.begin());
            active_nodes.erase(active_nodes.find(it));
        }
     
        return ans;
    }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i=0;i<s.size();i++) {
      |                     ~^~~~~~~~~

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