Submission #1213168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213168		TroySer	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	105 ms	16012 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;
using ll = long long;

ll cntAndMerge(vector<ll>& A, ll l, ll m, ll r) {
  
    ll nLeft = m - l + 1, nRight = r - m;
    
    vector<ll> L(nLeft), R(nRight);
    for (ll i = 0; i < nLeft; i++) {
        L[i] = A[i + l];
    }
    for (ll j = 0; j < nRight; j++) {
        R[j] = A[m + 1 + j];
    }

    ll res = 0;
    ll i = 0, j = 0, k = l;

    while (i < nLeft && j < nRight) {

        if (L[i] <= R[j]) {
            A[k] = L[i];
            k++; i++;
        } else {
            A[k] = R[j];
            k++; j++;
            res += nLeft - i;
        }
    }

    while (i < nLeft) {
        A[k] = L[i];
        k++; i++;
    } 
    
    while (j < nRight) {
        A[k] = R[j];
        k++; j++;
    }

    return res;
}

ll cntInversions(vector<ll>& arr, ll l, ll r) {

    ll res = 0;
    
    if (l < r) {

        ll m = (r + l) / 2;

        res += cntInversions(arr, l, m);
        res += cntInversions(arr, m + 1, r);

        res += cntAndMerge(arr, l, m, r);

    }

    return res;

}

ll inversionCount(vector<ll> &arr) {

  	ll N = arr.size();
  	return cntInversions(arr, 0, N - 1);

}

ll count_swaps(vector<int> shoes) {

    ll N = shoes.size();
    
    ll negPointer = 0;

    vector<ll> currentShoesRelative;
    currentShoesRelative.resize(N);

    map<ll, priority_queue<ll, vector<ll>, greater<ll> > > mapOfPQs;
    for (ll i = 0; i < N; i++) {
        if (shoes[i] > 0) {
            mapOfPQs[shoes[i]].push(i);
        }
    }

    for (ll i = 0; i < N; i++) {
        if (shoes[i] < 0) {
            currentShoesRelative[i] = negPointer;
            ll nextNearest = mapOfPQs[-shoes[i]].top();
            mapOfPQs[-shoes[i]].pop();
            currentShoesRelative[nextNearest] = negPointer + 1;
            negPointer += 2;
        }
    }

    // for (ll i = 0; i < N; i++) {
    //     cout << currentShoesRelative[i] << " ";
    // }
    // cout << endl;

    return inversionCount(currentShoesRelative);

}

// int main() {
//     cout << count_swaps({-3, 2, 1, -1, -2, 2, -2, 3}) << endl;
// }

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