Submission #742678

#	Time	Username	Problem	Language	Result	Execution time	Memory
742678		fang	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	242 ms	274916 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
int tree[200010];
queue<int> q1[200010];
queue<int> q2[200010];
int visited[200010];
int read(int idx)
{
	int sum=0;
	while(idx>0)
	{
		sum+=tree[idx];
		idx-=(idx&-idx);
	}
	return sum;
}
void update(int idx,int val,int n)
{
	while(idx<=n)
	{
		tree[idx]+=val;
		idx+=(idx&-idx);
	}
}
long long count_swaps(std::vector<int> s) {
	int n=s.size();
	long long sum=0;
	for(int i=1;i<=n;i++) update(i,1,n);
	for(int i=1;i<=n;i++)
	{
		if(s[i-1]>0) q1[s[i-1]].push(i);
		else q2[-s[i-1]].push(i);
	} 
	for(int i=1;i<=n;i++)
	{
		if(visited[i]) continue;
		update(i,-1,n);
		visited[i]++;
		if(s[i-1]<0)
		{
			int x=-s[i-1];
			int idx=q1[x].front();
			q1[x].pop();
			q2[x].pop();
			while(visited[idx])
			{
				q1[x].pop();
				idx=q1[x].front();
			} 
			sum+=read(idx)-1;
			if(idx<i) sum++;
			update(idx,-1,n);
			visited[idx]++;
			//printf("idx=%d sum=%d i=%d\n",idx,sum,i);
		}
		else 
		{
			int x=s[i-1];
			int idx=q2[x].front();
			q2[x].pop();
			q1[x].pop();
			while(visited[idx])
			{
				q2[x].pop();
				idx=q2[x].front();
			} 
			sum+=read(idx)-1;
			if(idx>i) sum++;
			update(idx,-1,n);
			//update(i,-1,n);
			visited[idx]++;
			//printf("idx=%d sum=%d i=%d\n",idx,sum,i);
		}
		// for(int i=1;i<=n;i++)
		// {
		// 	printf("%d ",read(i)-read(i-1));
		// }
		// printf("\n");
		
	}
	return sum;
}

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