Submission #443461

#	Time	Username	Problem	Language	Result	Execution time	Memory
443461		rainboy	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	62 ms	13764 KiB

shoes

#include "shoes.h"
#include <stdlib.h>

using namespace std;

typedef vector<int> vi;

int abs_(int a) { return a > 0 ? a : -a; }

const int N = 100000;

int *ei[N * 2 + 1], eo[N * 2 + 1];

void append(int a, int i) {
	int o = eo[a]++;

	if (o >= 2 && (o & o - 1) == 0)
		ei[a] = (int *) realloc(ei[a], o * 2 * sizeof *ei[a]);
	ei[a][o] = i;
}

int ft[N * 2];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int rr[N * 2];

long long count_swaps(vi aa) {
	int n = aa.size() / 2, i, j, a, b, o;
	long long ans;

	for (a = 0; a <= n * 2; a++)
		ei[a] = (int *) malloc(2 * sizeof *ei[a]);
	for (i = 0; i < n * 2; i++)
		append(aa[i] + n, i);
	ans = 0;
	for (a = 0; a < n; a++) {
		b = n * 2 - a;
		for (o = 0; o < eo[a]; o++) {
			i = ei[a][o], j = ei[b][o];
			if (i < j)
				rr[i] = j, rr[j] = -1;
			else
				rr[j] = i, rr[i] = -1, ans++;
		}
	}
	for (i = 0; i < n * 2; i++)
		if (rr[i] != -1) {
			ans += rr[i] - i - 1 - (query(rr[i] - 1) - query(i - 1));
			update(rr[i], n * 2, 1);
		}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'void append(int, int)':
shoes.cpp:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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