Submission #159201

#	Time	Username	Problem	Language	Result	Execution time	Memory
159201		Bilyana	Arranging Shoes (IOI19_shoes)	C++17	65 / 100	221 ms	142824 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 input()
{
    long long temp;
    cin>>n;
    for (long long i=0; i<2*n; i++)
    {
        cin>>temp;
        s.push_back(temp);
    }
}*/

void output()
{
    cout<<counter<<endl;
}

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)
            {
                //cout<<i<<' '<<bs[temp].front()<<endl;
                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);
        /*for (long long j=0; j<from[i]; j++)
        {
            swap(to[j], to[j+1]);
            counter++;
        }*/
    }
}

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;
}

/*long long main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    solve();
    output();
    return 0;
}*/

/*
3
-2 2 2 -2 -2 2
*/

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