Submission #704490

#	Time	Username	Problem	Language	Result	Execution time	Memory
704490		firewater	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	145 ms	144112 KiB

shoes

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 202300
#include "shoes.h"
 
using namespace std;
 
ll n,x,y,ans,c[N],p[N];
queue<ll>d[N];
void add(ll x,ll y)
{
	x++;
	for(;x<=n*2;x+=x&-x)
		c[x]+=y;
	return;
}
ll ask(ll x)
{
	x++;
	ll sum=0;
	for(;x;x-=x&-x)
		sum+=c[x];
	return sum;
}
long long count_swaps(std::vector<int> s) {
	n=s.size()/2;
	ans=0;
	for(ll i=2*n-1;i>=0;--i){
		add(i,1);
		x=s[i];
		d[x+n].push(i);
	}
	for(ll i=2*n-1;i>=0;--i){
		if(p[i])continue;
		x=s[i];
		y=-s[i];
		if(x<0)ans++;
		ll j=d[y+n].front();
		d[x+n].pop();
		d[y+n].pop();
		
		ans+=ask(i-1)-ask(j);
		add(i,-1);
		add(j,-1);
		p[i]=1;
		p[j]=1;
	}
	return ans;
}
//int main()
//{
//	vector<int>aaa;
//	aaa.push_back(2);
//	aaa.push_back(1);
//	aaa.push_back(-1);
//	aaa.push_back(-2);
//	printf("%lld\n",count_swaps(aaa));
//	return 0;
//}

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