Submission #1032549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032549		omarpaladines95	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1099 ms	3896 KiB

shoes

#include "shoes.h"

#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;
}

bool IsValid(const std::vector<int>& curPermutation)
{
    for (int i = 0; i < curPermutation.size(); i+=2)
    {
        if(!((curPermutation[i] < 0) && (curPermutation[i+1] > 0) && ((curPermutation[i] + curPermutation[i+1]) == 0)))
        {
            return false;
        }
    }
    return true;
}

long long count_swaps(std::vector<int> S)
{
    long long minSwaps = LLONG_MAX;
    vector<int> curPermutation = S;
    sort(curPermutation.begin(), curPermutation.end());
    do
    {
        if (IsValid(curPermutation))
        {
            minSwaps = min(minSwaps, FindNumberOfSwaps(S, curPermutation));
        }
    } while(next_permutation(curPermutation.begin(), curPermutation.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:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if ((i == target.size()) && (j == target.size()))
      |              ~~^~~~~~~~~~~~~~~~
shoes.cpp:18:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if ((i == target.size()) && (j == target.size()))
      |                                      ~~^~~~~~~~~~~~~~~~
shoes.cpp:25:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     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:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if (startingIndex == target.size())
      |             ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
shoes.cpp: In function 'bool IsValid(const std::vector<int>&)':
shoes.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < curPermutation.size(); i+=2)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~

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