Submission #1066192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066192		Tsovak	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	131 ms	139720 KiB

shoes

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;

// -------------------- Typedefs -------------------- //

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;

// -------------------- Defines -------------------- //

#define pr pair
#define mpr make_pair
#define ff first
#define ss second

#define mset multiset
#define mmap multimap
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pqueue priority_queue

#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()

#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back

#define lb lower_bound
#define ub upper_bound
#define bs binary_search

// -------------------- Constants -------------------- //

const int MAX = int(1e9 + 5);
const ll MAXL = ll(1e18 + 5);
const ll MOD = ll(1e9 + 7);
const ll MOD2 = ll(998244353);

// -------------------- Solution -------------------- //

const int N = 100005;
int f[N * 2];
deque<int> c[N * 2];
bool used[N * 2];
int n;

void upd(int ind)
{
	for (int i = ind; i < n * 2; i |= (i + 1)) f[i]++;
	return;
}

int qry(int ind)
{
	int ans = 0;
	for (int i = ind; i >= 0; i = (i & (i + 1)) - 1) ans += f[i];
	return ans;
}

int qry(int l, int r)
{
	int ans = qry(r);
	if (l) ans -= qry(l - 1);
	return ans;
}

ll count_swaps(vector<int> a)
{
	int i, j;

	n = sz(a) / 2;

	for (i = 0; i < n * 2; i++) {
		if (a[i] > 0) c[a[i]].pb(i);
		else c[n - a[i]].pb(i);
	}

	/*for (i = 1;i <= n * 2;i++) {
		for (auto j : c[i]) cout << j << ' ';
		cout << "\n";
	}*/

	ll ans = 0;

	for (i = 0; i < n * 2; i++) {
		if (used[i]) continue;

		if (a[i] < 0) {
			j = c[-a[i]].ft();
			c[-a[i]].popf();
			c[n - a[i]].popf();

			used[j] = true;
			upd(j);
			ans += j - i - 1 - qry(i + 1, j - 1);
		}
		else {
			j = c[n + a[i]].ft();
			c[n + a[i]].popf();
			c[a[i]].popf();

			used[j] = true;
			upd(j);
			ans += j - i - 1 - qry(i + 1, j - 1) + 1;
		}
		//cout << ans << "\n";
	}

	return ans;
}

/*
	# # # #   # # # #   # # # #   #       #    #       #     #
	   #      #         #     #    #     #    # #      #   #
	   #      # # # #   #     #     #   #    #   #     # #
	   #            #   #     #      # #    # # # #    #   #
	   #      # # # #   # # # #       #    #       #   #     #
*/

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