Submission #222879

#	Time	Username	Problem	Language	Result	Execution time	Memory
222879		MrDomino	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	13 ms	9984 KiB

shoes

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

using namespace std;

typedef long long ll;

ll get_dist(vector<int> ord)
{
    ll sol = 0;
    for (int i = 0; i < (int) ord.size(); i++)
    {
        int j = i;
        while (ord[j] != i)
        {
            j++;
        }
        while (j > i)
        {
            swap(ord[j], ord[j - 1]);
            sol++;
            j--;
        }
    }
    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++)
    {
        pl[a[i]].push_back(i);
        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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15