Submission #1308016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308016		afric	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 KiB

shoes

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

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

pair<vector<long long>, long long> bubbleSortSwaps(vector<long long> &a,long long l, long long r)
{
    // alter merge sort to simulate bubble sort
    if (l==r) // base case - single item covered
    {
        return {{a[l]},0};
    }
    long long mid = (l+r)/2;
    pair<vector<long long>, long long> left = bubbleSortSwaps(a,l,mid);
    pair<vector<long long>, long long> right = bubbleSortSwaps(a,mid+1,r);
    long long inv = left.second + right.second;
    vector<long long> merged;
    long long i = 0; // right pointer
    long long 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<long long> &a, map<long long,vector<long long>> &index)
{
    long long maxValue = (*index.rbegin()).first;
    vector<long long> pointers(maxValue+1,0);
    for (long long i = 0; i < a.size(); i++)
    {
        if (index.find(a[i])==index.end())
        {
            continue; //  we've already modified this item, so skip it.
        }
        long long 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<long long> s)
{
    map<long long,vector<long long>> index; // array of index occurrences
    // for o(1) finding of left-right pairs
    for (long long i = 0; i < s.size(); i++)
    {
        if (index.find(s[i])==index.end())
        {
            index[s[i]] = {i};
        }
        else{
            index[s[i]].push_back(i);
        }
    }
    removeDuplicates(s,index);
    vector<long long> sorting(s.size(), -1); // blank arr
    map<long long,long long> indexNew;
    for (long long i = 0; i < s.size(); i++)
    {
        indexNew[s[i]] = i;
    }
    long long nextLeft = 0;
    for (long long 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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccIhjfWz.o: in function `main':
grader.cpp:(.text.startup+0x26b): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status