Submission #603964

#	Time	Username	Problem	Language	Result	Execution time	Memory
603964		boris_mihov	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	154 ms	140340 KiB

shoes

#include <iostream>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 100000 + 10;

int a[2*MAXN], n;
int fenwick[2*MAXN];
void update(int pos)
{
    for (int i = pos ; i <= n ; i += i & (-i))
    {
        fenwick[i]++;
    }
}

int query(int pos)
{
    int sum = 0;
    for (int i = pos ; i >= 1 ; i -= i & (-i))
    {
        sum += fenwick[i];
    }

    return sum;
}

int realPos(int pos)
{
    return pos + query(n) - query(pos-1);
}

bool taken[2*MAXN];
std::queue <int> q[2*MAXN];
llong count_swaps(std::vector <int> s)
{
    n = s.size();
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = s[i-1];
        q[MAXN + a[i]].push(i);
    }

    llong ans = 0, currPos = 1, next = 2;
    for (int i = 1 ; i <= n ; i += 2)
    {
        if (a[currPos] > 0)
        {
            q[MAXN + a[currPos]].pop();
            int take = q[MAXN - a[currPos]].front();
            q[MAXN - a[currPos]].pop();
            ans += realPos(take) - realPos(currPos);
            taken[currPos] = true;
            taken[take] = true;
            update(take);
        } else
        {
            if (a[next] != -a[currPos])
            {
                q[MAXN + a[currPos]].pop();
                int take = q[MAXN - a[currPos]].front();
                q[MAXN - a[currPos]].pop();
                ans += realPos(take) - realPos(next);
                taken[currPos] = true;
                taken[take] = true;
                update(take);
            } else
            {
                q[MAXN + a[currPos]].pop();
                q[MAXN + a[next]].pop();
                while (taken[next]) ++next;
                currPos = next;
                ++next;
                while (taken[next]) ++next;
            }
        }

        while (taken[next]) ++next;
        currPos = next;
        ++next;
        while (taken[next]) ++next;
    }

    return ans;
}

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