Submission #690967

#	Time	Username	Problem	Language	Result	Execution time	Memory
690967		finn__	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	81 ms	16548 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#include "shoes.h"

struct FenwickTree
{
    vector<int> t;

    FenwickTree(size_t n)
    {
        t = vector<int>(n, 0);
    }

    void prefix_increment(int i, int x)
    {
        i++;
        while (i <= t.size())
        {
            t[i - 1] += x;
            i += i & -i;
        }
    }

    void range_increment(int i, int j, int x)
    {
        prefix_increment(i, x);
        if (j < t.size() - 1)
            prefix_increment(j + 1, -x);
    }

    int point_query(int i)
    {
        i++;
        int x = 0;
        while (i)
        {
            x += t[i - 1];
            i -= i & -i;
        }
        return x;
    }
};

long long count_swaps(vector<int> s)
{
    size_t const n = s.size();
    vector<bool> processed(n, 0);
    vector<priority_queue<unsigned, vector<unsigned>, greater<unsigned>>> q(n);
    for (unsigned i = 0; i < n; i++)
        q[2 * (abs(s[i]) - 1) + (s[i] < 0)].push(i);

    long long swaps_needed = 0;
    FenwickTree tree(n);

    for (unsigned i = 0; i < n; i++)
    {
        if (!processed[i])
        {
            processed[i] = 1;
            while (processed[q[2 * (abs(s[i]) - 1) + (s[i] > 0)].top()])
                q[2 * (abs(s[i]) - 1) + (s[i] > 0)].pop();
            unsigned j = q[2 * (abs(s[i]) - 1) + (s[i] > 0)].top();
            q[2 * (abs(s[i]) - 1) + (s[i] > 0)].pop();
            processed[j] = 1;
            swaps_needed += j + tree.point_query(j) - i - tree.point_query(i) - (s[i] < 0);
            tree.range_increment(i, j, 1);
        }
    }

    return swaps_needed;
}

Compilation message (stderr)

shoes.cpp: In member function 'void FenwickTree::prefix_increment(int, int)':
shoes.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
shoes.cpp: In member function 'void FenwickTree::range_increment(int, int, int)':
shoes.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if (j < t.size() - 1)
      |             ~~^~~~~~~~~~~~~~

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