Submission #873517

#	Time	Username	Problem	Language	Result	Execution time	Memory
873517		Cutebol	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	348 KiB

shoes

	#include "shoes.h"
	#include <bits/stdc++.h>
	using namespace std ;

	const int N = 2e5 + 5 ;

	map <int , set <int>> l , r ;
	bool f[N] ;

	long long count_swaps(vector<int> s) {
		int n = s.size() , ans = 0 ;
		for ( int i = 0 ; i < n ; i ++ ){
			if ( s[i] < 0 ) l[-s[i]].insert(i) ;
			else r[s[i]].insert(i) ;
		}
		for ( int i = 0 ; i < n ; i ++ ){
			if ( f[i] == 1 ) continue ;
			if ( s[i] < 0 ){
				int ind = *r[-s[i]].begin() ;
				r[-s[i]].erase(r[-s[i]].begin()) ;
				l[-s[i]].erase(l[-s[i]].begin()) ;
				ans += ind-i-1 ;
				f[ind] = 1 ;
			}
			else{
				int ind = *l[s[i]].begin() ;
				l[s[i]].erase(l[s[i]].begin()) ;
				r[s[i]].erase(r[s[i]].begin()) ;
				ans += ind-i ;
				f[ind] = 1 ;
			}
		}
		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