Submission #1311213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311213		dimitri.shengelia	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	228 ms	30964 KiB

shoes

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

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

map <long long, vector <long long>> mp;

long long count_swaps ( vector <int> S ) {

	vector <int> a = S;

	long long n = a.size();

	ordered_set <long long> st;

	vector <bool> visited( n, false );

	long long answer = 0;

	for ( long long i = 0; i < n; i++ ) {

		mp[a[i]].push_back( i );

	}

	for ( long long i = 0; i < n; i++ ) {

		if ( visited[i] == true ) {

			continue;

		}

		long long j = i;

		long long x = a[i], y = -1 * a[i];
		long long z = mp[y][0];

		visited[z] = true;

		auto it = st.lower_bound( z );

		if ( it == st.end() ) {

			z -= st.size();

		} else {

			z -= st.order_of_key( *it );

		}

		it = st.lower_bound( i );

		if ( it == st.end() ) {

			j -= st.size();

		} else {

			j -= st.order_of_key( *it );

		}

		answer += z - j - 1;

		if ( x > 0 ) {

			answer++;

		}

		st.insert( i );
		st.insert( z );

		mp[x].erase( mp[x].begin() );
		mp[y].erase( mp[y].begin() );

	}

	return answer;

}

/*
//#include "shoes.h"
#include <cstdio>
#include <cassert>

using namespace std;

int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
*/

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