제출 #213076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
213076		iris2617	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	265 ms	280132 KiB

shoes

#include "shoes.h"
#include <queue>
using namespace std;

int arr[100010],n;
queue<int> q[100010],q2[100010];
int bit[100010];
bool used[100010];

void build()
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(i+(i&(-i))<=n)
		{
			bit[i+(i&(-i))]+=bit[i];
		}
	}
}

void add(int a,int k)
{
	int i;
	for(i=a;i<=n;i+=(i&(-i)))
	{
		bit[i]+=k;
	}
}

int sum(int a)
{
	int i,res=0;
	for(i=a;i;i-=(i&(-i)))
	{
		res+=bit[i];
	}
	return res;
}

long long count_swaps(std::vector<int> s)
{
	int i,ans,a;
	ans=0;
	
	n=s.size();
	for(i=1;i<=n;i++)
	{
		a=s[i-1];
		if(a<0)
		{
			q[-a].push(i);
		}
		else
		{
			q2[a].push(i);
		}
		arr[i]=a;
		bit[i]=1;
	}
	build();
	for(i=1;i<=n;i++)
	{
		if(used[i])
		{
			continue;
		}
		used[i]=1;
		
		if(arr[i]>0)
		{
			add(q[arr[i]].front(),-1);
			add(i,-1);
			ans+=sum(q[arr[i]].front())+1;
			used[q[arr[i]].front()]=1;
		}
		else
		{
			arr[i]*=-1;
			add(q2[arr[i]].front(),-1);
			add(i,-1);
			ans+=sum(q2[arr[i]].front());
			used[q2[arr[i]].front()]=1;
		}
		q[arr[i]].pop();
		q2[arr[i]].pop();
	}
	return ans;
}

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