Submission #289827

#	Time	Username	Problem	Language	Result	Execution time	Memory
289827		IgorI	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	129 ms	13304 KiB

shoes

#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <cstdlib>
#include <iostream>
#include <map>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int (i) = 0; (i) < (n); (i)++)

const int N = 540400;

int fenw[N];

void add(int pos)
{
    while (pos < N)
    {
        fenw[pos]++;
        pos = (pos | (pos + 1));
    }
}

int get(int pos)
{
    int res = 0;
    while (pos >= 0)
    {
        res += fenw[pos];
        pos = (pos & (pos + 1)) - 1;
    }
    return res;
}

long long count_swaps(vector<int> a)
{
    int n = a.size() / 2;
    long long ans = 0;
    set<pair<int, int> > s;
    for (int i = 0; i < a.size(); i++)
    {
        s.insert({a[i], i});
    }
    for (int i = 0; i < n; i++)
    {
        auto it = s.begin();
        pair<int, int> x = *it;
        s.erase(s.begin());
        auto it2 = s.lower_bound({-x.first, -1});
        pair<int, int> y = *it2;
        //cout << x.first << " " << x.second << "->" << y.first << " " << y.second << "\n";
        s.erase(y);
        int real_pos = y.second + get(a.size()) - get(y.second);
        add(y.second);
        ans += abs(real_pos - (2 * i + 1));
        if (x.first > 0) ans++;
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~

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