Submission #1311260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311260		dimitri.shengelia	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	579 ms	49696 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;
map <long long, long long> mp1;

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 );

		mp1[a[i]] = 0;

	}

	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][mp1[y]];

		visited[z] = true;

		auto it = st.upper_bound( i );

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

			j += st.size() - st.order_of_key( *it );

		}

		auto it1 = st.upper_bound( z );

		if ( it1 != st.end() ) {

			z += st.size() - st.order_of_key( *it1 );

		}

		answer += z - j - 1;

		if ( x > 0 ) {

			answer++;

		}

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

		mp1[x]++;
		mp1[y]++;

	}

	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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15