Submission #1093246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093246		emptypringlescan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	98 ms	72912 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
long long fenw[200005];
void update(int x){
	for(;x<200005;x+=x&-x) fenw[x]++;
}
long long query(int x){
	long long ret=0;
	for(;x;x-=x&-x) ret+=fenw[x];
	return ret;
}
long long count_swaps(vector<int> arr){
	int n=arr.size()/2;
	int corr[n*2];
	queue<int> prev[n+5];
	for(int i=0; i<n*2; i++){
		if(prev[abs(arr[i])].empty()||(prev[abs(arr[i])].front()<0&&arr[i]<0)||(prev[abs(arr[i])].front()>0&&arr[i]>0)){
			if(arr[i]<0) prev[abs(arr[i])].push(-i-1);
			else prev[abs(arr[i])].push(i+1);
		}
		else{
			//cout << prev[abs(arr[i])].front() << ' ' << arr[i] << '\n';
			corr[abs(prev[abs(arr[i])].front())-1]=i;
			corr[i]=abs(prev[abs(arr[i])].front())-1;
			prev[abs(arr[i])].pop();
		}
	}
	//for(int i=0; i<n*2; i++) cout << corr[i] << ' ';
	long long ans=0;
	for(int i=0; i<n*2; i++){
		if(corr[i]<i) continue;
		ans+=corr[i]-i-(query(corr[i])-query(i));
		if(arr[i]<0) ans--;
		update(corr[i]);
	}
	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