Submission #467506

#	Time	Username	Problem	Language	Result	Execution time	Memory
467506		alextodoran	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	85 ms	14052 KiB

shoes

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#include "shoes.h"

using namespace std;

typedef long long ll;

ll count_swaps (vector <int> s)
{
    int n = (int) s.size() / 2;

    {
        vector <vector <int>> l (n);
        vector <vector <int>> r (n);
        for(int i = 0; i < n * 2; i++)
        {
            int x = abs(s[i]) - 1;
            if(s[i] < 0)
                l[x].push_back(i);
            else
                r[x].push_back(i);
        }

        int curr = 0;
        for(int x = 0; x < n; x++)
        {
            sort(l[x].begin(), l[x].end());
            sort(r[x].begin(), r[x].end());

            for(int i = 0; i < (int) l[x].size(); i++)
            {
                curr++;

                s[l[x][i]] = -curr;
                s[r[x][i]] = curr;
            }
        }
    }

    vector <int> first (n, -1);

    vector <ll> BIT (n * 2, 0);

    function <void (int)> update = [&] (int pos)
    {
        pos++;
        for(int i = pos; i <= n * 2; i += i & -i)
            BIT[i - 1]++;
    };

    function <ll (int)> query = [&] (int pos)
    {
        pos++;
        ll sum = 0;
        for(int i = pos; i >= 1; i -= i & -i)
            sum += BIT[i - 1];
        return sum;
    };

    ll answer = 0;

    for(int i = 0; i < n * 2; i++)
    {
        int x = abs(s[i]) - 1;

        if(first[x] == -1)
        {
            first[x] = i;

            update(first[x]);

            if(s[i] > 0)
                answer++;
        }
        else
        {
            answer += query(i) - query(first[x]);

            update(first[x]);
        }
    }

    return answer;
}

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