Submission #1213155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213155		LolkasMeep	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	119 ms	75196 KiB

shoes

#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;

ll countMerge(vector<int>& arr, int l, int m, int r){
    int n1 = m-l+1;
    int n2 = r-m;

    vector<int> left(n1);
    vector<int> right(n2);

    for(int i = 0; i < n1; i++) left[i] = arr[i+l];
    for(int i = 0; i < n2; i++) right[i] = arr[m + 1 + i];

    ll res = 0;
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else {
            arr[k++] = right[j++];
            res += (n1 - i);
        }
    }
    
    while (i < n1) arr[k++] = left[i++];
    while (j < n2) arr[k++] = right[j++];

    return res;
}

ll countInv(vector<int>& arr, int l, int r){
    ll res = 0;
    if (l < r) {
        int m = (r + l) / 2;
        res += countInv(arr, l, m);
        res += countInv(arr, m + 1, r);
        res += countMerge(arr, l, m, r);
    }
    return res;
}

ll count_swaps(vector<int> S){
    int n = S.size() / 2;
    if(n == 1){
        if(S[0] < 0) return 0;
        return 1;
    }

    int neg = 0;

    unordered_map<int, deque<int>> qs;
    vector<int> poop(n*2);

    for(int i = 0; i < n*2; i++){
        if(S[i] < 0){
            qs[abs(S[i])].push_back(neg);
            poop[i] = neg;
            neg += 2;
        }
    }

    // for(auto [a, aa] : qs){
    //     cout << a << ": ";
    //     for (int b : aa) {
    //         cout << b << " ";
    //     }
    //     cout << '\n';
    // }

    for(int i = 0; i < n*2; i++){
        if(S[i] > 0){
            poop[i] = qs[S[i]].front() + 1;
            qs[S[i]].pop_front();
        }
    }

    // for(int i = 0; i < n*2; i++){
    //     cout << poop[i] << ' ';
    // }
    // cout << '\n';

    return countInv(poop, 0, n*2-1);

}

// int main(){

//     cout << count_swaps({2, 1, -1, -2});

//     return 0;
// }

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