Как посчитать количество инверсий, используя сортировку слиянием?

Question

[Никита]

Добрый вечер. Решил задачу и с полной уверенностью загрузил ее в проверяющую систему. В итоге неправильный ответ на 7 тесте.
Не могли бы, пожалуйста, помочь?
Мой код:

#include <iostream>
#include <fstream>
int* input_array(int* len)
{
	std::ifstream fin;
	fin.open("inversions.in");
	fin >> *len;
	int* array = new int[*len];
	for (int i = 0; i < *len; i++)
		fin >> array[i];
	fin.close();
	return array;
}

void Merge_Sort(int* array, int array_size, int* number_of_inversitions)
{
	if (array_size <= 1) return;

	int middle = array_size / 2;
	int left_size = middle;
	int right_size = array_size - middle;
	int* left = array;
	int* right = array + left_size;

	Merge_Sort(left, left_size, number_of_inversitions);
	Merge_Sort(right, right_size, number_of_inversitions);

	int left_index = 0;
	int right_index = 0;
	int index = 0; 
	int* temp_array = new int[array_size];
	while (left_index < left_size and right_index < right_size)
	{
		if (left[left_index] <= right[right_index])
			temp_array[index++] = left[left_index++];
		else {
			temp_array[index++] = right[right_index++];
			*number_of_inversitions += left_size - left_index;
		}
	}

	while (left_index < left_size)
		temp_array[index++] = left[left_index++];
	while (right_index < right_size)
		temp_array[index++] = right[right_index++];

	for (int i = 0; i < array_size; i++)
		array[i] = temp_array[i];
	delete[] temp_array;
}

int main()
{
	std::ofstream fout;
	fout.open("inversions.out");
	int number_of_inversitions = 0, n;
	int* array;
	array = input_array(&n);
	Merge_Sort(array, n, &number_of_inversitions);
	fout << number_of_inversitions;
	delete[] array;
	fout.close();
	return 0;
}

Answer 1

[Wataru]

Вроде все правильно. Какие ограничения? Может быть переполнение, ведь максимальный ответ n(n-1)/2. Для переполнения int достаточно 65536 чисел в массиве.

Comments

[Никита]

Ограничения такие: кол-во элементов в массиве <= 100000 и числа не превышают 10^9

[Никита]

А почему именно 65536? Не совсем понятен этот момент

[Wataru]

Никита, Если массив упорядочен по убыванию, то каждая пара чисел даст инверсию. Всего пар n(n-1)/2. В int помещается 2^31. Решаем уравнение n(n-1)/2=2^31. Или n(n-1)=2^32. Для больших чисел можно грубо прикинуть просто взяв корень, получим, что n~2^16=65536. На самом деле ответ где-то между 65536 и 65537, т.е. я на 1 ошибся - для переполнения нужно 65537 упорядоченных по убыванию чисел.

У вас в задаче может быть 100 тысяч чисел, что больше 65 тысяч, поэтому на максимальном тесте ваше решение переполнит счетчик инверсий и выдадет неправильный ответ.

Поменяйте number_of_inversitions на 64-битный тип и должно заработать.

[Никита]

Илья Николаевский, Большое спасибо за подробное объяснение) Исправил, теперь все работает