Submission #143878

#	Time	Username	Problem	Language	Result	Execution time	Memory
143878		stoyan_malinin	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1085 ms	146804 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)
        {
            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 bestLeft[MAXN], bestRight[MAXN];

int calcValue(int num, int index)
{
    int sum = (bestLeft[num] - index) + (bestRight[num] - (index+1));
    if(bestLeft[num]>bestRight[num]) 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);
    }

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

        bestIndex = abs(s[*allIndexes.begin()]);
        bestLeft[bestIndex] = leftShoes[bestIndex].front() - T->query(leftShoes[bestIndex].front());leftShoes[bestIndex].pop();
        bestRight[bestIndex] = rightShoes[bestIndex].front() - T->query(rightShoes[bestIndex].front());rightShoes[bestIndex].pop();

        T->update(bestLeft[bestIndex], 1);
        T->update(bestRight[bestIndex], 1);

        allIndexes.erase(bestLeft[bestIndex]);
        allIndexes.erase(bestRight[bestIndex]);

        //cout << "   " << bestIndex << '\n';

        answer += calcValue(bestIndex, 0);
    }

    //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:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.size();i++)
                   ~^~~~~~~~~
shoes.cpp:70: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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15