Submission #1214056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214056		TroySer	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	861 ms	172688 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() / 2;

    // {index, isNegative}
    map<ll, priority_queue<ll, vector<ll>, greater<ll> > > mapOfPQs;
    map<ll, queue<ll> > mapOfStack;

    for (ll i = 0; i < 2 * N; i++) {
        mapOfPQs[shoes[i]].push(i);
        mapOfStack[shoes[i]].push(i);
    }

    vector<ll> supposedPosition;
    vector<bool> alreadyConsidered(2 * N, false);
    supposedPosition.reserve(2*N);
    for (ll i = 0; i < 2 * N; i++) { // just place them where they're meant to be

        if (alreadyConsidered[i]) continue;

        ll firstPosition = mapOfPQs[shoes[i]].top();
        mapOfPQs[shoes[i]].pop();
        ll secondPosition = mapOfPQs[-shoes[i]].top();
        mapOfPQs[-shoes[i]].pop();

        supposedPosition.push_back(shoes[i]);
        supposedPosition.push_back(-shoes[i]);

        alreadyConsidered[firstPosition] = true;
        alreadyConsidered[secondPosition] = true;

    }
    
    vector<ll> meantToBe(2 * N);
    for (ll i = 0; i < 2 * N; i++) {
        meantToBe[i] = mapOfStack[supposedPosition[i]].front();
        mapOfStack[supposedPosition[i]].pop();
    }

    // did not care about negative/positive until now

    ll extraMoves = 0;
    for (ll i = 0; i < 2 * N; i+=2) {
        if (supposedPosition[i] > supposedPosition[i + 1]) {
            extraMoves++;
        }
    }

    return inversionCount(meantToBe) + extraMoves;

}

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