Submission #715739

#	Time	Username	Problem	Language	Result	Execution time	Memory
715739		ovidiush11	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	173 ms	141780 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

#define ll long long

#include "shoes.h"

long long count_swaps(std::vector<int> v)
{
	ll n = v.size(),ans = 0;
	vector<queue<ll>> a(n+1);
	for(ll i = 0;i < n;i++)
    {
        if(!a[abs(v[i])].empty())
        {
            if(v[i] == v[a[abs(v[i])].front()])a[abs(v[i])].push(i);
            else
            {
                if(v[a[abs(v[i])].front()] > 0)ans++;
                v[a[abs(v[i])].front()] = i;
                a[abs(v[i])].pop();
                v[i] = -1;
            }
        }else a[abs(v[i])].push(i);
    }
    ll tree[2*n] = {0},g = n,k = 0,s = 0;
    while(g != 1)
    {
        if(g % 2 == 1)s=1;
        g /= 2;
        k++;
    }
    k += s;
    k = pow(2,k);
    for(ll i = 0;i < n;i++)
    {
        if(v[i] != -1)
        {
            ans += v[i] - i - 1;
            ll pos1,pos2,t1 = 0,t2 = 0;
            if(i < (n-k/2)*2)pos1 = k + i;
            else pos1 = k/2 + i - (n-k/2);
            if(v[i] < (n-k/2)*2)pos2 = k + v[i];
            else pos2 = k/2 + v[i] - (n-k/2);
            if(pos1 >= k && pos2 < k)
            {
                if(pos1 % 2 == 1)t1 = 1;
                pos1 /= 2;
            }
            while(pos1 != pos2)
            {
                if(pos1 % 2 == 1)
                {
                    if(t1 == 0)ans -= tree[pos1];
                    t1 = 1;
                }
                else if(t1 != 0 && pos2 != pos1 + 1)ans -= tree[pos1+1];
                if(pos2 % 2 == 0)
                {
                    if(t2 == 0)ans -= tree[pos2];
                    t2 = 1;
                }
                else if(t2 != 0 && pos2 != pos1 + 1)ans -= tree[pos2-1];
                tree[pos2]++;
                pos1 /= 2;pos2 /= 2;
            }
            if(t1 == 0 && t2 == 0)ans -= tree[pos1];
            else if(t1 == 0)ans -= tree[pos1*2];
            else if(t2 == 0)ans -= (tree[pos1*2+1] - 1);
            while(pos1 != 1)
            {
                tree[pos1]++;
                pos1 /= 2;
            }
            tree[pos1]++;
        }
    }
    return ans;
}

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