Skip to content

Instantly share code, notes, and snippets.

@nullkal
Last active Dec 22, 2015
Embed
What would you like to do?
クロッシング問題の回答。計測位置間違えてそうなことに提出後に気づいた。 普通にマージソートで転倒数求めてます。Rubyでやったら配列の確保とかに時間かかってるっぽかったので、修正も面倒だしC++で書き直しました。途中までin-placeなマージソートの実装追い求めてましたが、色々頭が混乱してきたので最終的に至って普通のマージソートになりました。
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <cstdint>
std::vector<int> buf;
std::uintmax_t answer = 0;
void merge(int *arr, size_t arr1_size, size_t arr2_size)
{
using namespace std;
copy(arr, arr + arr1_size + arr2_size, buf.begin());
int *arr1 = &buf[0];
int *arr1_end = arr1 + arr1_size;
int *arr2 = arr1_end;
int *arr2_end = arr2 + arr2_size;
for (; arr1 < arr1_end && arr2 < arr2_end; ++arr)
{
if (*arr1 < *arr2)
{
*arr = *arr1;
arr1 += 1;
} else
{
*arr = *arr2;
arr2 += 1;
answer += arr1_end - arr1;
}
}
for (; arr1 < arr1_end; ++arr, ++arr1)
{
*arr = *arr1;
}
for (; arr2 < arr2_end; ++arr, ++arr2)
{
*arr = *arr2;
}
}
void sort(int *arr, size_t size)
{
if (size <= 1) return;
size_t half_size = size / 2;
int *arr1 = arr;
size_t arr1_size = half_size;
sort(arr1, arr1_size);
int *arr2 = arr + half_size;
size_t arr2_size = size - half_size;
sort(arr2, arr2_size);
merge(arr, arr1_size, arr2_size);
}
int main(int argc, char *argv[])
{
std::vector<int> perm;
perm.reserve(524288);
buf.reserve(524288);
for (;;)
{
int num;
std::cin >> num;
if (std::cin.eof()) break;
perm.push_back(num);
}
namespace chrono = std::chrono;
auto begin = chrono::system_clock::now();
sort(&perm[0], perm.size());
auto end = chrono::system_clock::now();
auto wall_time =
chrono::duration_cast<chrono::second>(end - begin);
std::cout
<< answer << "," << wall_time.count() << std::endl
<< "ENV: C++" << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment