Submission #921802

#	Time	Username	Problem	Language	Result	Execution time	Memory
921802		Nurislam	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	93 ms	10612 KiB

shoes

#include "shoes.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;

#define order_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
long long count_swaps(std::vector<int> a) {
	int n = a.size()/2;
	int la[n*2]{};
	int b[n+1]{};
	for(int i = n*2-1; i >= 0; i--){
		if(b[abs(a[i])] == 0)b[abs(a[i])] = i;
		else{
			la[i] = b[abs(a[i])];
			b[abs(a[i])] = 0;
		}
	}
	order_set st;
	int ans = 0, us[n*2]{};
	for(int i = 0; i < n*2; i++){
		if(us[i]){
			st.erase(i);
			continue;
		}
		int r = st.order_of_key(la[i]);
		ans += la[i]-i-1-r;
		st.insert(la[i]);
		us[la[i]]++;
	}
	int us2[n*2]{};
	for(int i = 0; i < n*2; i++){
		if(us2[i])continue;
		us2[la[i]]++;
		ans += (a[i] > 0);
	}
	return ans;
}

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