Submission #722847

#	Time	Username	Problem	Language	Result	Execution time	Memory
722847		victor_gao	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	252 ms	274860 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
deque<int>all[200015][2];
int n,out[200015];
struct BIT{
	int arr[200015];
	void modify(int p,int c){
		for (;p<=n;p+=(p&-p))
			arr[p]+=c;
	}
	int query(int p){
		int ans=0;
		for (;p>0;p-=(p&-p))
			ans+=arr[p];
		return ans;
	}
}bit;
long long count_swaps(std::vector<int> s) {
	n=s.size();
	for (int i=0;i<n;i++){
		if (s[i]<0) all[abs(s[i])][0].push_back(i+1);
		else all[s[i]][1].push_back(i+1);
		bit.modify(i+1,1);
	}
	long long ans=0;
	for (int i=1;i<=n;i++){
		if (out[i]) continue;
		if (s[i-1]<0){
			int nxt=all[abs(s[i-1])][1].front();
			int realp1=bit.query(i),realp2=bit.query(nxt); out[nxt]=1; out[i]=1;
			if (realp1>realp2)
				ans=(ans+realp1-realp2);
			else 
				ans=(ans+realp2-realp1-1);
		//	cout<<realp1<<" "<<realp2<<' ';
			bit.modify(i,1);
			bit.modify(nxt+1,-1);
		}
		else {
			int nxt=all[s[i-1]][0].front();
			int realp1=bit.query(nxt),realp2=bit.query(i); out[nxt]=1; out[i]=1;
			if (realp1>realp2)
				ans=(ans+realp1-realp2);
			else 
				ans=(ans+realp2-realp1-1);
		//	cout<<realp1<<" "<<realp2<<" ";
			bit.modify(i,1);
			bit.modify(nxt+1,-1);
		}
		all[abs(s[i-1])][1].pop_front();
		all[abs(s[i-1])][0].pop_front();
	//	cout<<ans<<'\n';
	}
	return ans;
}

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