Submission #143875

#	Time	Username	Problem	Language	Result	Execution time	Memory
143875		stoyan_malinin	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1079 ms	270516 KiB

shoes

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

using namespace std;

const int MAXN = 2e5 + 5;

struct fenwickTree
{
    int tree[MAXN];

    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 moveElement(int i, int j, vector <int> &s)
{
    int cnt = 0;
    while(j>i)
    {
        cnt++;

        swap(s[j-1], s[j]);
        j--;
    }

    return cnt;
}

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)
{
    for(int i = 0;i<s.size();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)
    {
        //memset(bestLeft, -1, sizeof(bestLeft));

        /*
        for(int i = s.size()-1;i>=index;i--)
        {
            if(s[i]<0) bestLeft[ -s[i] ] = i;
            else bestRight[ s[i] ] = i;
        }
        */


        int bestIndex = -1;


        bestIndex = abs(s[index]);
        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);

        //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:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.size();i++)
                   ~^~~~~~~~~
shoes.cpp:80: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