Submission #1213106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213106		TroySer	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	328 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 posPointer = 0, negPointer = 1;

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

    for (ll i = 0; i < N; i++) {
        if (shoes[i] < 0) {
            currentShoesRelative[negPointer] = negPointer;
            negPointer += 2;
        } else if (shoes[i] > 0) {
            currentShoesRelative[posPointer] = posPointer;
            posPointer += 2;
        }
    }

    return inversionCount(currentShoesRelative);

}

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