Submission #299021

#	Time	Username	Problem	Language	Result	Execution time	Memory
299021		REALITYNB	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	144 ms	80528 KiB

shoes

#include <bits/stdc++.h> 
using namespace std; 
const int mxn = 1e5+1 ; 
vector<int> ft(mxn) ; 
void update(int i ){
	for(;i<mxn;i+=(i&-i)) ft[i]++ ; 
}
int query(int i ){
	int ans = 0 ; 
	for(;i>0;i-=(i&-i)) ans+=ft[i] ; 
	return ans ; 
}
long long count_swaps(vector<int> a){
#define int long long 
	int n = a.size() ;
	int ans = 0  ; 
	set<int> adj[n*3] ; 
	for(int i=0;i<n;i++) adj[a[i]+n].insert(i) ;  
	for(int i=0;i<n;i++){
		if(a[i]==0) continue ; 
	//	cout <<a[i] << " " ; 
		int oth = a[i]*-1 ; 
		oth+=n ; 
		a[i]+=n ; 
		adj[a[i]].erase(i) ; 
		int j = *(adj[oth].begin()) ; 
		adj[oth].erase(adj[oth].begin()) ; 
		int ze = query(j+1)-query(i+1) ; 
		ans+=j-i-(a[i]-n<0)-ze ;
		a[i]=0 ; 
		a[j]= 0 ; 
		update(1+i) ; 
		update(j+1) ; 
	}
//	cout << ans ; 
	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