Submission #159202

#	Time	Username	Problem	Language	Result	Execution time	Memory
159202		Bilyana	Arranging Shoes (IOI19_shoes)	C++17	65 / 100	240 ms	142848 KiB

shoes

#include<iostream>
#include<queue>
#include<cmath>

using namespace std;

const long long MAXN = 200000;
long long n, to[MAXN+10], from[MAXN+10];
queue<long long> bs[MAXN+10];
long long fw[MAXN+10];
long long counter=0;

void find_place(vector<int> S)
{
    long long curr = 0;
    long long temp;
    for (long long i=0; i<n; i++)
    {
        temp = abs(S[i]);
        if (S[i]>0)
        {
            if (!bs[temp].empty() && bs[temp].front()%2==0)
            {
                to[i] = bs[temp].front()+1;
                bs[temp].pop();
            }
            else
            {
                to[i] = curr+1;
                bs[temp].push(curr+1);
                curr += 2;
            }
        }
        else
        {
            if (!bs[temp].empty() && bs[temp].front()%2==1)
            {
                to[i] = bs[temp].front()-1;
                bs[temp].pop();
            }
            else
            {
                to[i] = curr;
                bs[temp].push(curr);
                curr += 2;
            }
        }
    }
}

void calc_from()
{
    for (long long i=0; i<n; i++)
    {
        from[to[i]] = i;
    }
}

void update(long long curr, long long dif)
{
    curr++;
    while(curr>0)
    {
        fw[curr] += dif;
        curr -= (curr&(-curr));
    }
}

long long sum(long long curr)
{
    curr++;
    long long sm = 0;
    while (curr<MAXN)
    {
        sm += fw[curr];
        curr += (curr&(-curr));
    }
    return sm;
}

void sorting()
{
    for (long long i=0; i<n; i++)
    {
        long long curr = sum(from[i]) + from[i];
        counter += abs(curr-i);
        update(from[i],1);
    }
}

void solve(vector<int> S)
{
    n = S.size();
    find_place(S);
    calc_from();
    sorting();
}

long long count_swaps(vector<int> S)
{
    solve(S);
    return counter;
}

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