Submission #159182

#	Time	Username	Problem	Language	Result	Execution time	Memory
159182		Bilyana	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	214 ms	138464 KiB

shoes

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

using namespace std;

const long long MAXN = 100000;
long long n, to[MAXN+10];
queue<long long> bs[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 sorting()
{
    for (long long i=0; i<n; i++)
    {
        long long nd=i;
        while (to[nd]!=i && nd<n) nd++;
        //cout<<i<<" - ";
        while (nd!=i)
        {
            //cout<<nd<<' ';
            swap(to[nd], to[nd-1]);
            counter++;
            nd--;
        }
        //cout<<endl;
    }
}

void solve(vector<int> S)
{
    n = S.size();
    find_place(S);
    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: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15