Submission #143888

#	Time	Username	Problem	Language	Result	Execution time	Memory
143888		stoyan_malinin	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	401 ms	147704 KiB

shoes

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<set>

using namespace std;

const int MAXN = 1e5 + 5;

struct fenwickTree
{
    int tree[MAXN*2];

    fenwickTree()
    {
        memset(this->tree, 0, sizeof(this->tree));
    }

    void update(int index, int value)
    {
        index++;
        while(index<MAXN*2)
        {
            this->tree[index] += value;
            index += index&(-index);
        }
    }

    int query(int index)
    {
        int sum = 0;

        index++;
        while(index>0)
        {
            sum += this->tree[index];
            index -= index&(-index);
        }

        return sum;
    }
};

fenwickTree *T = new fenwickTree();
queue <int> leftShoes[MAXN], rightShoes[MAXN];

int calcValue(int num, int index, int bestLeft, int bestRight)
{
    int sum = (bestLeft - index) + (bestRight - (index+1));
    if(bestLeft>bestRight) sum++;

    return sum;
}

long long count_swaps(vector <int> s)
{
    set <int> allIndexes;
    for(int i = 0;i<s.size();i++)
    {
        allIndexes.insert(i);

        if(s[i]<0) leftShoes[ -s[i] ].push(i);
        else rightShoes[ s[i] ].push(i);
    }

    long long answer = 0;
    for(int index = 0;index<s.size();index+=2)
    {
        int bestIndex = -1;
        int bestLeft, bestRight;

        bestIndex = abs(s[*allIndexes.begin()]);
        allIndexes.erase(leftShoes[bestIndex].front());
        allIndexes.erase(rightShoes[bestIndex].front());

        bestLeft = leftShoes[bestIndex].front() - T->query(leftShoes[bestIndex].front());
        bestRight = rightShoes[bestIndex].front() - T->query(rightShoes[bestIndex].front());

        T->update(leftShoes[bestIndex].front(), 1);
        T->update(rightShoes[bestIndex].front(), 1);

        leftShoes[bestIndex].pop();
        rightShoes[bestIndex].pop();

        //cout << bestLeft << " " << bestRight << '\n';

        answer += calcValue(bestIndex, 0, bestLeft, bestRight);
    }

    //for(int i = 0;i<s.size();i++) cout << s[i] << " ";
    //cout << '\n';

    return answer;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.size();i++)
                   ~^~~~~~~~~
shoes.cpp:68:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int index = 0;index<s.size();index+=2)
                       ~~~~~^~~~~~~~~

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