Submission #307911

#	Time	Username	Problem	Language	Result	Execution time	Memory
307911		mihai145	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	262 ms	25212 KiB

shoes

#include "shoes.h"
#include <vector>
#include <set>

const int NMAX = 1e5;

int N;
int shoes[2 * NMAX + 2];

std::vector<int> l[NMAX + 2], r[NMAX + 2];
std::set<int> pos;

int aib[2 * NMAX + 2];

inline int LSB(int x)
{
    return x & -x;
}

void Update(int pos, int val)
{
    for(int i = pos; i <= N; i += LSB(i))
        aib[i] += val;
}

int Query(int pos)
{
    int ans = 0;

    for(int i = pos; i > 0; i -= LSB(i))
        ans += aib[i];

    return ans;
}

long long count_swaps(std::vector<int> s) {

    N = (int)s.size();

    for(int i = 0; i < N; i++)
        {
            shoes[i + 1] = s[i];
            if(shoes[i + 1] < 0)
                l[-shoes[i + 1]].push_back(i + 1);
            else
                r[shoes[i + 1]].push_back(i + 1);

            pos.insert(i + 1);
        }

    for(int i = 1; i <= N; i++)
        Update(i, 1);

    long long swaps = 0LL;

    for(int i = 1; i <= N / 2; i++)
        {
            int p = *pos.rbegin();

            if(shoes[p] > 0)
                {
                    ///rightShoo
                    swaps += 1LL * (Query(N) - Query(l[shoes[p]].back()) - 1);

                    pos.erase(p);
                    pos.erase(l[shoes[p]].back());

                    Update(p, -1);
                    Update(l[shoes[p]].back(), -1);

                    l[shoes[p]].pop_back();
                    r[shoes[p]].pop_back();
                }
            else
                {
                    ///leftShoo
                    swaps += 1LL * (Query(N) - Query(r[-shoes[p]].back()));

                    pos.erase(p);
                    pos.erase(r[-shoes[p]].back());

                    Update(p, -1);
                    Update(r[-shoes[p]].back(), -1);

                    l[-shoes[p]].pop_back();
                    r[-shoes[p]].pop_back();
                }
        }

    return swaps;
}

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