제출 #603959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
603959		boris_mihov	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	90 ms	134956 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(currPos);
                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;
}

// 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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15