Submission #1214049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214049		TroySer	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 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<pair<ll, bool>, vector<pair<ll, bool> >, greater<pair<ll, bool> > > > mapOfPQs;
    map<ll, queue<ll> > mapOfStack;

    vector<int> shoesWithNoSigns(2 * N);
    for (ll i = 0; i < 2 * N; i++) {
        shoesWithNoSigns[i] = abs(shoes[i]);
        mapOfPQs[shoesWithNoSigns[i]].push({i, shoes[i] < 0});
        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;

        auto [firstPosition, firstIsNegative] = mapOfPQs[shoesWithNoSigns[i]].top();
        mapOfPQs[shoesWithNoSigns[i]].pop();
        auto [secondPosition, secondIsNegative] = mapOfPQs[shoesWithNoSigns[i]].top();
        mapOfPQs[shoesWithNoSigns[i]].pop();

        supposedPosition.push_back(shoesWithNoSigns[i] * (firstIsNegative ? -1 : 1));
        supposedPosition.push_back(shoesWithNoSigns[i] * (secondIsNegative ? -1 : 1));

        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();
    }

    // for (ll i = 0; i < 2 * N; i++) {
    //     cout << supposedPosition[i] << " ";
    // }
    // cout << endl;
    // for (ll i = 0; i < 2 * N; i++) {
    //     cout << meantToBe[i] << " ";
    // }
    // cout << endl;

    // 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;

}

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

Compilation message (stderr)

/usr/bin/ld: /tmp/ccHCCCru.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc1qf6R1.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status