Submission #257449

#	Time	Username	Problem	Language	Result	Execution time	Memory
257449		StevenH	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	3 ms	2688 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int x,a[MAXN],n;
inline int lowbit(int x)
{
	return x&(-x);
}
void add(int x)
{
	while(x<=n)
	{
		a[x]++;
		x+=lowbit(x);
	}
	return;
}
int pre(int x)
{
	int ans = 0;
	while(x>0)
	{
		ans+=a[x];
		x-=lowbit(x);
	}
	return ans;
}
int query(int x,int y)
{
	return pre(y)-pre(x-1);
}
vector<vector<int> > rpos(MAXN);
bool vis[MAXN];
long long count_swaps(std::vector<int> s) {
		
	n = s.size();
	
	s.push_back(0);
	for(int i=n;i>=1;i--)
		s[i]=s[i-1];
	
	for(int i=1;i<=n;i++)
		if(s[i]>0)
			rpos[s[i]].push_back(i);	
		
	int sum=0,cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]<0)
		{
			int ss = -s[i];
			sum+=i+query(i+1,n)-1-cnt;
			add(i);
			for(int j=0;j<(int)rpos[ss].size();j++)
			{
				int pos = rpos[ss][j];
				if(vis[pos])continue;
				vis[pos]=1;
				sum+=pos-(cnt+2)+query(pos+1,n);
				add(pos);
			}
			cnt+=2;
		}
	}
	return sum;
}

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