Submission #1148049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148049		gulmix	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	143 ms	27004 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>

struct BIT{
    vector<ll> bit;
    ll n;
    BIT(){}
    BIT(ll n): n(n){
        bit.resize(n + 1, 0);
    }
    void update(ll u, ll x){
        for(u; u <= n; u += (u & -u))bit[u]+=x;
    }
    ll get(ll u){
        ll ans = 0;
        for(u; u > 0; u -= (u & -u))ans += bit[u];
        return ans;
    }
    ll get(ll l, ll r){
        return get(r) - get(l-1);
    }
};

vector<ll> d[200007];
vector<ll> l[200007], r[200007];

bool cmp(vector<ll> a, vector<ll> b) {
    return min(a[0], a[1]) < min(b[0], b[1]);
}

ll count_swaps(vector<int> s) {
    for(int i = 0; i < s.size(); i++) {
        if(s[i] < 0) {
            l[-s[i]].push_back(i + 1);
        } else {
            r[s[i]].push_back(i + 1);
        }
    }
    ll n = s.size() / 2;
    ll c = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < l[i].size(); j++) {
            d[++c].push_back(r[i][j]);
            d[c].push_back(l[i][j]);
        }
    }
    sort(d + 1, d + c + 1, cmp);
    BIT bit = BIT(s.size() + 1);
    ll ans = 0;
    for(int i = 1; i <= c; i++) {
        for(int j = 1; j >= 0; j--) {
            ll pos = i * 2 - j;
            ll sus = d[i][j] + bit.get(d[i][j] + 1, s.size());
            bit.update(d[i][j], 1);
            ans += abs(sus - pos);
        }
    }
    return ans;
}

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