Submission #157556

#	Time	Username	Problem	Language	Result	Execution time	Memory
157556		lukameladze	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	715 ms	673616 KiB

shoes

# include <bits/stdc++.h>
using namespace std;
long long n,a[100005],pas,tree[100005],ans,w,w1,fix[100005];
queue <long long> q[10][100005];
void inc (int ind,int val)
{
    for (int i=ind; i<=2*n;  i+=(i&(-i)))
    {
        tree[i]+=val;
    }
}
int sum (int ind)
{
    pas=0;
    for (int i=ind; i>0; i-=(i&(-i)))
    pas+=tree[i];
    
    return pas;
}
int count_swaps(std::vector <int> v)
{
	n=v.size()/2;
	for (int i=1; i<=2*n; i++)
	{
		a[i]=v[i-1];
		if (a[i]>=0)
		{
			q[1][a[i]].push(i);
		}
		else
		{
			q[0][-a[i]].push(i);
		}
	}
	for(int i=1; i<=2*n; i++)
	{
			if (a[i]>=0)
			{
				fix[i]=1;
				if (fix[q[0][a[i]].front()]==0)
				{
					inc(i,1);
				}
				else
				{
				     inc(q[0][a[i]].front(),1);
					if (q[1][a[i]].size()==0 || q[0][a[i]].size()==0)
					{
						continue;
					}
					else
					{
						w=q[1][a[i]].front();
						w1=q[0][a[i]].front();
						q[1][a[i]].pop();
						q[0][a[i]].pop();
						ans+=sum(i-1)-sum(w1);
					}
				}
			}
			else
			{
			     ans++;
				fix[i]=1;
				if (fix[q[1][-a[i]].front()]==0)
				{
					inc(i,1);
					
				}
				else
				{
				     inc(q[1][-a[i]].front(),1);
					if (q[1][-a[i]].size()==0 || q[0][-a[i]].size()==0)
					{
						continue;
					}
					else
					{
						w=q[1][-a[i]].front();
						w1=q[0][-a[i]].front();
						q[1][-a[i]].pop();
						q[0][-a[i]].pop();
						ans+=sum(i-1)-sum(w);
						
					}
				}
			}
	}
	return ans;
}

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