Submission #1033359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033359		omarpaladines95	Arranging Shoes (IOI19_shoes)	C++14	30 / 100	1096 ms	5332 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

void FindFirstSwap(std::vector<int>& original_copy, const std::vector<int>& target, int& startingIndex, long long& numSwaps)
{
    int i = 0;
    int j = 0;
    startingIndex = target.size();
    while (original_copy[i] == target[j])
    {
        ++i;
        ++j;

        // If we reached the end and they match, we can just return.
        if ((i == target.size()) && (j == target.size()))
        {
            break;
        }
    }

    // Now we need to advance i until it matches.
    for (int start = i; start < target.size(); ++start)
    {
        if(target[j] == original_copy[start])
        {
            i=start;
            break;
        }
    }

    startingIndex = i;
    numSwaps = i-j;
}

long long FindNumberOfSwaps(const std::vector<int>& original, const std::vector<int>& target)
{
    long long totalSwaps = 0;
    std::vector<int> original_copy = original;

    // We will keep modifying original_copy until we swap everything.
    while (true)
    {
        int startingIndex = target.size();
        long long numSwaps = 0;
        FindFirstSwap(original_copy, target, startingIndex, numSwaps);
        totalSwaps += numSwaps;
        if (startingIndex == target.size())
        {
            break;
        }
        else
        {
            // Apply the swaps.
            for (int i = 0; i < numSwaps; ++i)
            {
                int localCopy = original_copy[startingIndex];
                original_copy[startingIndex] = original_copy[startingIndex-1];
                original_copy[startingIndex - 1] = localCopy;
                startingIndex--;
            }
        }
    }
    return totalSwaps;
}

long long count_swaps(std::vector<int> S)
{
    long long minSwaps = LLONG_MAX;
    vector<int> validPermutation;

    for (int i = 0; i < S.size(); ++i)
    {
        if(S[i] > 0)
        {
            validPermutation.push_back(S[i]);
        }
    }
    sort(validPermutation.begin(), validPermutation.end());

    do
    {
        std::vector<int> expandedValidPermutation(S.size());
        for (int i = 0; i < validPermutation.size(); ++i)
        {
            expandedValidPermutation[2*i] = -validPermutation[i];
            expandedValidPermutation[2*i+1] = validPermutation[i];
        }
        minSwaps = min(minSwaps, FindNumberOfSwaps(S, expandedValidPermutation));
    } while(next_permutation(validPermutation.begin(), validPermutation.end()));
    return minSwaps;
}

Compilation message (stderr)

shoes.cpp: In function 'void FindFirstSwap(std::vector<int>&, const std::vector<int>&, int&, long long int&)':
shoes.cpp:16:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if ((i == target.size()) && (j == target.size()))
      |              ~~^~~~~~~~~~~~~~~~
shoes.cpp:16:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if ((i == target.size()) && (j == target.size()))
      |                                      ~~^~~~~~~~~~~~~~~~
shoes.cpp:23:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int start = i; start < target.size(); ++start)
      |                         ~~~~~~^~~~~~~~~~~~~~~
shoes.cpp: In function 'long long int FindNumberOfSwaps(const std::vector<int>&, const std::vector<int>&)':
shoes.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if (startingIndex == target.size())
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < S.size(); ++i)
      |                     ~~^~~~~~~~~~
shoes.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 0; i < validPermutation.size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~

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