Submission #922085

#	Time	Username	Problem	Language	Result	Execution time	Memory
922085		Nurislam	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	196 ms	142852 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]{};
	queue<int> pos[n+1], neg[n+1];
	for(int i = 0; i < n*2; i++){
		int x = a[i];
		if(x < 0){
			if(!pos[-a[i]].empty()){
				la[pos[-a[i]].front()] = i;
				pos[-a[i]].pop();
			}else{
				neg[-a[i]].push(i);
			}
		}else{
			if(!neg[a[i]].empty()){
				la[neg[a[i]].front()] = i;
				neg[a[i]].pop();
			}else{
				pos[a[i]].push(i);
			}
		}
	}
	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]);
		if(r < (int)st.size() && *st.find_by_order(r) < la[a[i]])r++;
		ans += la[i]-i-r;
		if(a[i] < 0)ans--;
		st.insert(la[i]);
		us[la[i]]++;
	}
	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