Submission #1308024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308024		afric	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1098 ms	46212 KiB

shoes

// https://oj.uz/problem/view/IOI19_shoes

#include <bits/stdc++.h>
using namespace std;

pair<vector<int>, long long> bubbleSortSwaps(vector<int> a,int l, int r)
{
    // alter merge sort to simulate bubble sort
    if (l==r) // base case - single item covered
    {
        return {{a[l]},0};
    }
    int mid = (l+r)/2;
    pair<vector<int>, long long> left = bubbleSortSwaps(a,l,mid);
    pair<vector<int>, long long> right = bubbleSortSwaps(a,mid+1,r);
    long long inv = left.second + right.second;
    vector<int> merged;
    int i = 0; // right pointer
    int j = 0; // left pointer
    while (j < left.first.size() && i < right.first.size())
    {
        // take element from left
        if (right.first[i] >= left.first[j])
        {
            merged.push_back(left.first[j]);
            j++;
        }
        // take element from right.
        else{
            merged.push_back(right.first[i]);
            i++;
            inv += (left.first.size()-j);
        }
    }
    // left pointer exceeds boundary so we add all right
    while (i < right.first.size())
    {
        merged.push_back(right.first[i]);
        i++;
    }
    while (j < left.first.size())
    {
        merged.push_back(left.first[j]);
        j++;
    }

    return {merged, inv};
}

void removeDuplicates(vector<int> &a, unordered_map<int,vector<int>> &index, int maxValue)
{
    map<int,int> pointers;
    for (auto p : index)
    {
        pointers[p.first] = 0;
    }
    for (int i = 0; i < a.size(); i++)
    {
        if (index.find(a[i])==index.end())
        {
            continue; //  we've already modified this item, so skip it.
        }
        int p = pointers[abs(a[i])];
        if (index[a[i]].size() - p > 1) // duplicates are present for this value.
        {
            pointers[abs(a[i])]++;
            if (a[i] > 0)
            {
                a[index[0-a[i]][p]] = (0-(maxValue+1));
                a[i] = maxValue+1;
            }
            else{
                a[index[0-a[i]][p]] = maxValue+1;
                a[i] = (0-(maxValue+1));
            }
            maxValue++;
        }
    }
}


long long count_swaps(vector<int> s)
{
    unordered_map<int,vector<int>> index; // array of index occurrences
    // for o(1) finding of left-right pairs
    int maxValue = INT_MIN;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] > maxValue)
        {
            maxValue = s[i];
        }
        if (index.find(s[i])==index.end())
        {
            index[s[i]] = {i};
        }
        else{
            index[s[i]].push_back(i);
        }
    }
    removeDuplicates(s,index,maxValue);
    vector<int> sorting(s.size(), -1); // blank arr
    unordered_map<int,int> indexNew;
    for (int i = 0; i < s.size(); i++)
    {
        indexNew[s[i]] = i;
    }
    int nextLeft = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (sorting[i] != -1)
        {
            continue; // skip already chosen vals
        }
        if (s[i] > 0) // right shoe.
        {
            sorting[i] = nextLeft+1;
            sorting[indexNew[0-s[i]]] = nextLeft;
        }
        else{ // left shoe
            sorting[i] = nextLeft;
            sorting[indexNew[0-s[i]]] = nextLeft+1;
        }
        nextLeft+=2;
    }
    return bubbleSortSwaps(sorting, 0, sorting.size()-1).second;
}

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