Submission #906324

#	Time	Username	Problem	Language	Result	Execution time	Memory
906324		bobbilyking	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	695 ms	44024 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;
    F(i, 0, s.size()) {
        positions[s[i]].insert(i);
        active_nodes.insert(i);
    }
    ll ans = 0;
    
    F(i, 0, n) {
        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:5:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define F(i, l, r) for (ll i = l; i < (r); ++i)
      |                                     ^
shoes.cpp:26:5: note: in expansion of macro 'F'
   26 |     F(i, 0, s.size()) {
      |     ^

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