Submission #154396

#	Time	Username	Problem	Language	Result	Execution time	Memory
154396		rama_pang	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	111 ms	13924 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct bit {
    ll n;
    vector<ll> tree;
    bit(ll n) {
        this->n = n;
        tree.assign(n + 5, 0);
        for (ll i = 1; i <= n; i++) add(i, 1);
    }
    void add(ll x, ll v) {
        for (ll i = x; i <= n; i += i&-i) {
            tree[i] += v;
        }
    }

    ll ask(ll x) {
        ll res = 0;
        for (ll i = x; i > 0; i -= i&-i) {
            res += tree[i];
        }
        return res;
    }
};

ll count_swaps(vector<int> s) {
    ll N = s.size() / 2;
    vector<pair<ll, ll>> solve;
    vector<vector<pair<ll, ll>>> shoes(N + 5);
    for (ll i = 0; i < s.size(); i++) {
        shoes[abs(s[i])].push_back({s[i], i + 1});
    }
    
    ll res = 0; //optimal solution = greedily switch left shoes to the end, and nearest right shoe
    for (ll i = 1; i <= N; i++) { //then recursively do the same, but don't disturb the first pair
        sort(shoes[i].begin(), shoes[i].end()); //use fenwick tree for n log n
        ll lim = shoes[i].size() / 2;
        for (ll j = 0; j < lim; j++) {
            ll le = shoes[i][j].second;
            ll ri = shoes[i][j + lim].second;
            if (le > ri) swap(le, ri), res++;
            solve.push_back({le, ri});
        }
    }
    sort(solve.begin(), solve.end());
    bit bit(2 * N);
    for (auto i : solve) {
        res += bit.ask(i.second - 1) - bit.ask(i.first);
        bit.add(i.second, -1);
        bit.add(i.first, -1);
    }
    return res;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll 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