Submission #440816

#	Time	Username	Problem	Language	Result	Execution time	Memory
440816		QuantumK9	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1096 ms	74804 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair

vector<pair<int, int> > lft;
map<int, queue<int> > rgt;

long long count_swaps(vector<int> s) {
	//nums
	ll n = s.size()/2;
	ll S = s.size();

	//iterate through s -- preprocess
	for( int i = 0; i < S; i++ ){
		if( s[i] < 0 ){ lft.pb( mp(s[i], i) ); } //left shoe 
		else if ( s[i] > 0 ){  rgt[s[i]].push(i); } //right shoe
	}

	bool idim[S];
	memset( idim, true, sizeof idim );

	//process
	ll grand = 0;
	for( int i = 0; i < n; i++ ){

		for( int j = 0; j < lft[i].second; j++ ){ grand += idim[j]; }
		idim[ lft[i].second ] = false;

		for( int j = 0; j < rgt[ abs(lft[i].first) ].front(); j++){ grand += idim[j]; }
		idim[ rgt[abs(lft[i].first)].front() ] = false;
		rgt[abs(lft[i].first)].pop();

	}	

	return grand;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15