Submission #1206352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206352		jasonic	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 KiB

shoes

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

ll n;
vector<ll> toSort;

void conquer(int l_l, int l_r, int r_l, int r_r, ll &invCount) {
    ll szL = l_r - l_l + 1;
    ll szR = r_r - r_l + 1;

    queue<ll> a, b;
    queue<ll> res;
    for(int i = l_l; i <= l_r; i++) a.push(toSort[i]);
    for(int i = r_l; i <= r_r; i++) b.push(toSort[i]);

    while(szL && szR) {
        if(a.front() < b.front()) {
            res.push(a.front());
            a.pop();
            szL--;
        } else {
            res.push(b.front());
            b.pop();
            invCount += szL;
            szR--;
        }
    }

    while(szL) {
        res.push(a.front());
        a.pop();
        szL--;
    }

    while(szR) {
        res.push(b.front());
        b.pop();
        szR--;
    }

    for(int i = l_l; i <= r_r; i++) {
        toSort[i] = res.front();
        res.pop();
    }
}

void divide(int l, int r, ll &invCount) {
    if(l != r) {
        int m = l + (r-l)/2;
        divide(l, m, invCount);
        divide(m+1, r, invCount);
        conquer(l, m, m+1, r, invCount);
    }
}

ll count_swaps(vector<int> a) {
    n = size(a);
    /*

    we probably can find a solution that doesnt swap two left shoes
    
    l...r...L...R (no swap between l and L)
    l...r...R...l (no swap between l and L)

    l...L...R...r (swap r across LR)
    l...L...r...R (swap r across L)

    l...R...r...L (swap r across R, swap R across L?)
    l...R...L...r
      a   b   c
    goes to either lrLR or LRlr
    lrLR cost: a+b+c+b
    LRlr cost: b+a+b+c
    
    is it actually LMFAO

    lets see
    */

    vector<stack<ll>> spot(n+n+5);
    toSort = vector<ll>(n, -1);
    int x = 0;

    for(int i = 0; i < n; i++) {
        int pos = abs(a[i]);
        int neg = n + pos;

        if(a[i] < 0) {
            if(spot[pos].empty()) {
                spot[neg].push(i);
            } else {
                toSort[i] = x++;
                toSort[spot[pos].top()] = x++;
                spot[pos].pop();
            }
        } else {
            if(spot[neg].empty()) {
                spot[pos].push(i);
            } else {
                toSort[spot[neg].top()] = x++;
                toSort[i] = x++;
                spot[neg].pop();
            }
        }
    }

    ll invCount = 0;

    divide(0, n-1, invCount);

    return invCount;
}

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