Submission #873513

#	Time	Username	Problem	Language	Result	Execution time	Memory
873513		Cutebol	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	0 ms	444 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 , cnt = 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()) ;
			ans += (ind+cnt)-(i+1+cnt) ;
			f[ind] = 1 ;
		}
		else{
			int ind = *l[s[i]].begin() ;
			l[s[i]].erase(l[s[i]].begin()) ;
			ans += (ind+cnt)-(i+1+cnt)+1 ;
			f[ind] = 1 ;
		} cnt ++ ;
	}
	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