Submission #438737

#	Time	Username	Problem	Language	Result	Execution time	Memory
438737		faruk	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	288 KiB

shoes

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define ll long long
 
using namespace std;
 
class BIT
{
private:
vector<ll> tree;
int n;
public:
 
BIT(int sizeOfTree)
{
    n = sizeOfTree;
    tree.resize(n + 1, 0);
}
 
void update(int index, ll value)
{
    index++;
    while (index < n)
        tree[index] += value, index += index & (-index);
}
 
ll query(int index)
{
    index++;
    ll out = 0;
    while (index > 0)
        out += tree[index], index -= index & (-index);
    return out;
}
 
};
 
map<int, vector<int> > located;
map<int, int> used;
map<int, bool> matched;
 
ll count_swaps(vector<int> S)
{
    int n = S.size();
    BIT passed(n);
 
    for (int i = 0; i < n; i++)
        located[S[i]].push_back(i);
 
    ll out = 0;
    for (int i = 0; i < n; i++)
    {
        if (matched[i])
            continue;
        int counterpart = upper_bound(located[-S[i]].begin(), located[-S[i]].end(), used[-S[i]]) - located[-S[i]].begin();
        int val = located[-S[i]][counterpart];
        matched[val] = true;
        int swaps = (val - i) /*+ passed.query(val)*/;
        passed.update(val, 1);
        used[-S[i]] = val;
        used[S[i]] = i;
 
        if (S[i] < 0)
            swaps--;
        out += swaps;
    }
    return out;
}

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