Submission #159197

#	Time	Username	Problem	Language	Result	Execution time	Memory
159197		Bilyana	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	1080 ms	135164 KiB

shoes

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

using namespace std;

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

/*void input()
{
    int temp;
    cin>>n;
    for (int i=0; i<2*n; i++)
    {
        cin>>temp;
        s.push_back(temp);
    }
}*/

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

void find_place(vector<int> S)
{
    int curr = 0;
    int temp;
    for (int 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 (int i=0; i<n; i++)
    {
        from[to[i]] = i;
    }
}

void update(int curr, int dif)
{
    while(curr<n)
    {
        fw[curr] += dif;
        curr += curr&(-curr);
    }
}

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

void sorting()
{
    for (int i=0; i<n; i++)
    {
        int curr = sum(from[i]) + from[i];
        counter += abs(curr-i);
        update(from[i],1);
        /*for (int 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;
}

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

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

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