Submission #222884

#	Time	Username	Problem	Language	Result	Execution time	Memory
222884		MrDomino	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	100 ms	17004 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

typedef long long ll;

ll get_dist(vector<int> ord)
{
    int n = (int) ord.size();
    vector<int> aib(n + 1);
    ll sol = 0;
    for (int i = 0; i < n; i++)
    {
        sol += i;
        int x = ord[i] + 1, y = x;
        while (x)
        {
            sol -= aib[x];
            x -= x & (-x);
        }
        x = y;
        while (x <= n)
        {
            aib[x]++;
            x += x & (-x);
        }
    }
    return sol;
}

const int N = (int) 1e5 + 7;
vector<int> pl[N];
vector<int> mn[N];

struct T
{
    int l;
    int r;
};

bool operator < (T a, T b)
{
    return a.l + a.r < b.l + b.r;
}

long long count_swaps(vector<int> a)
{
    int n = (int) a.size() / 2;
    for (int i = 0; i < 2 * n; i++)
    {
        if (a[i] > 0)
        {
            pl[a[i]].push_back(i);
        } 
        if (a[i] < 0) 
        {
            mn[-a[i]].push_back(i);
        }
    }
    vector<T> p;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < (int) pl[i].size(); j++)
        {
            p.push_back({mn[i][j], pl[i][j]});
        }
    }
    sort(p.begin(), p.end());
    vector<int> ord;
    for (auto &it : p)
    {
        ord.push_back(it.l);
        ord.push_back(it.r);
    }
    return get_dist(ord);
}

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