Submission #332334

#	Time	Username	Problem	Language	Result	Execution time	Memory
332334		blue	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	113 ms	15724 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <vector>
using namespace std;

long long count_swaps(vector<int> S)
{
    int n = S.size()/2;

    long long res = 0;

    vector<int> left[n+1], right[n+1];

    vector<int> othershoe(2*n, -1);

    for(int i = 0; i < 2*n; i++)
    {
        if(S[i] < 0) left[-S[i]].push_back(i);
        else right[S[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < left[i].size(); j++)
        {
            if(left[i][j] < right[i][j]) othershoe[left[i][j]] = right[i][j];
            else
            {
                othershoe[right[i][j]] = left[i][j];
                res++;
            }
        }
    }

    vector<int> rightshift(2*n, 0);

    for(int i = 0; i < 2*n; i++)
    {
        if(othershoe[i] == -1) continue;

        res += othershoe[i] - i - 1;
        for(int j = i; j >= 1; j -= j&-j) res -= rightshift[j];
        for(int j = othershoe[i]; j >= 1; j -= j&-j) res += rightshift[j];

        for(int j = i+1; j < 2*n; j += j&-j) rightshift[j]++;
        for(int j = othershoe[i]+1; j < 2*n; j += j&-j) rightshift[j]--;
    }
    return res;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int j = 0; j < left[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~

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