Submission #921821

#	Time	Username	Problem	Language	Result	Execution time	Memory
921821		Nurislam	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	207 ms	144528 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 = n*2-1; i >= 0; i--){
		int x = a[i];
		if(x < 0){
			if(!pos[-a[i]].empty()){
				la[i] = pos[-a[i]].front();
				pos[-a[i]].pop();
			}else{
				neg[-a[i]].push(i);
			}
		}else{
			if(!neg[a[i]].empty()){
				la[i] = neg[a[i]].front();
				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]);
		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: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15