Submission #603945

#	Time	Username	Problem	Language	Result	Execution time	Memory
603945		boris_mihov	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1098 ms	138116 KiB

shoes

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

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

int a[MAXN], n;
int fenwick[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;
}

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

    llong ans = 0;
    for (int i = 1 ; i <= n ; i += 2)
    {
        if (a[i] > 0)
        {
            int last = a[i];
            for (int j = i+1 ; j <= n ; ++j)
            {
                int curr = a[j];
                a[j] = last; ++ans;
                if (curr == -a[i])
                {
                    a[i] = curr;
                    break;
                }

                last = curr;
            }
        }

        if (a[i+1] != -a[i])
        {
            int last = a[i+1];
            for (int j = i+2 ; j <= n ; ++j)
            {
                int curr = a[j];
                a[j] = last; ++ans;
                if (curr == -a[i])
                {
                    a[i+1] = curr;
                    break;
                }

                last = curr;
            }
        }
    }

    return ans;
}

// int N;
// std::vector <int> s;
// int main()
// {
//     std::cin >> N;
//     s.resize(N);
//     for (int i = 0 ; i < N ; ++i)
//     {
//         std::cin >> s[i];
//     }

//     std::cout << count_swaps(s) << '\n';
//     return 0;
// }

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