Submission #705204

#	Time	Username	Problem	Language	Result	Execution time	Memory
705204		stoyan_malinin	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	280 ms	148900 KiB

shoes

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

using namespace std;

const int MAXN = 1e5;

struct FenwickTree
{
    int tree[MAXN * 2 + 5];

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

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

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

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

        return sum;
    }
};

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

int calcValue(int leftShoeInd, int rightShoeInd)
{
    int val = leftShoeInd + (rightShoeInd - 1);
    if (leftShoeInd > rightShoeInd) val++;

    return val;
}

int64_t 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);
    }

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

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

        leftShoeFakeInd = leftShoes[bestIndex].front() - T->query(leftShoes[bestIndex].front());
        rightShoeFakeInd = 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();

        answer += calcValue(leftShoeFakeInd, rightShoeFakeInd);
    }

    return answer;
}

Compilation message (stderr)

shoes.cpp: In function 'int64_t count_swaps(std::vector<int>)':
shoes.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0;i<s.size();i++)
      |                    ~^~~~~~~~~
shoes.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     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