Submission #906250

#	Time	Username	Problem	Language	Result	Execution time	Memory
906250		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	85 / 100	215 ms	14756 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, ll> cnt;
    for (auto x: s) cnt[abs(x)]++;

	if (n <= 8) {
        vl perm; for (auto [k, v]: cnt) {
            v/=2;
            while(v-- ) perm.push_back(k);
        }
        sort(A(perm));
        ll ans = 1e9;
        do {
            vl ts(A(s));
            ll tans = 0;
            for (auto v: perm) {
                auto x = find(A(ts), -v);
                tans += x - ts.begin();
                ts.erase(x);
                x = find(A(ts), v);
                tans += x - ts.begin();
                ts.erase(x);
            }
            ans = min(ans, tans);

        } while (next_permutation(A(perm)));
        return ans;
    }
    if (cnt.size() == 1) {
        // subtask 3; thinking 
        set_t pos[2];
        F(i, 0, s.size()) if (s[i] < 0) pos[0].insert(i); else pos[1].insert(i);
        ll ans = 0;
        F(i, 0, n) {
            auto beg = pos[0].begin();
            pos[0].erase(pos[0].begin());
            ans += pos[1].order_of_key(*beg);
            beg = pos[1].begin();
            pos[1].erase(pos[1].begin());
            ans += pos[0].order_of_key(*beg);
        }
        return ans;
    }
    bool subtask4 = 1;
    F(i, 0, n) {
        subtask4 &= abs(s[i]) == abs(s[i + n]);
        subtask4 &= s[i] < 0;
        subtask4 &= s[i + n] > 0;
    }
    if (subtask4) return n * (n-1)/2;

    if (n <= 1000) {
        // typing stupid shit time
        ll ans = 0;
        F(i, 0, n) {
            auto it = find(s.begin() + 1, s.end(), -s[0]);
            if (s[0] < 0) {
                ans += it - s.begin() - 1;
                s.erase(it);
                s.erase(s.begin());
            } else {
                ans += it - s.begin();
                s.erase(it);
                s.erase(s.begin());
            }
        }
        return ans;
    }

    return -1;
}

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:52:9: note: in expansion of macro 'F'
   52 |         F(i, 0, s.size()) if (s[i] < 0) pos[0].insert(i); else pos[1].insert(i);
      |         ^

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