Submission #1200000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200000		AMel0n	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	324 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first 
// #define S second

#include "shoes.h"

ll N;
vector<ll> tree;

void update(ll v, ll p, ll tl = 0, ll tr = N-1, ll i = 1) {
    if (tl == tr) {tree[i] = v; return ;}
    ll tm = (tl + tr) / 2;
    if (p <= tm) update(v, p, tl, tm, i * 2);
    else update(v, p, tm + 1, tr, i * 2 + 1);
    tree[i] = tree[i * 2] + tree[i * 2 + 1];
}

ll query(ll l, ll r, ll tl = 0, ll tr = N-1, ll i = 1) {
    if (l > r) return 0;
    if (tl == l && tr == r) return tree[i];
    ll tm = (tl + tr) / 2;
    return query(l, min(r, tm), tl, tm, i * 2) + query(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
}


ll count_swaps(vector<int> S) {
    N = S.size();
    tree.resize(4*N);

    unordered_map<ll, queue<ll>> unpaired;
    FOR(i, N) unpaired[S[i]].push(i);

    vector<int> ok(N);
    int res = 0;
    // greedily pair shoes from the left
    FOR(i, N) {
        if (ok[i]) continue;
        ll j = unpaired[-S[i]].front();  // move shoe at pos j leftward to pos i or i + 1
        unpaired[-S[i]].pop();
        unpaired[S[i]].pop();
        res += j - i - 1 - query(i, j);
        if (S[i] > 0) res++; // right shoe - need extra swap
        update(1, j); 
        // val == 1: already moved to the left, dont double count swapping with it
        ok[j] = 1;
    }
    return 0;
}

// signed main() {
//     cin.tie(0); ios::sync_with_stdio(false);
    
// }

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