Submission #257605

#	Time	Username	Problem	Language	Result	Execution time	Memory
257605		StevenH	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	10 ms	9728 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define MAXN 200005
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),lpos(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);	
		else lpos[-s[i]].push_back(i);
		
	long long sum=0;
	int 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;
			vis[i]=1;
			//cout<<sum<<" ";
			add(i);
			for(int j=0;j<(int)rpos[ss].size();j++)
			{
				int pos = rpos[ss][j];
				if(vis[pos])continue;
				vis[pos]=1;
				//cout<<i<<" "<<pos<<endl;
				sum+=pos-(cnt+2)+query(pos+1,n);
				add(pos);
				//cout<<sum<<endl;
				break;
			}
			cnt+=2;
		}
		else if(s[i]>0)
		{
			int ss=s[i];
			sum+=(i-cnt-1)+query(i+1,n);
			add(i);
			vis[i]=1;
			for(int j=0;j<(int)lpos[ss].size();j++)
			{
				int pos = lpos[ss][j];
				if(vis[pos])continue;
				vis[pos]=1;
				sum+=pos-(cnt+2)+query(pos+1,n)+1;
				add(pos);
				break;
			}
			cnt+=2;
		}
	}
	return sum;
}

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