#include <algorithm>
#include <iostream>
#include <vector>
#include<algorithm>
#include<array>
#include<ios>
#include<iterator>
#include <chrono>
#include<queue>
#include<random>
#include<climits>
#include<cmath>
#include<type_traits>
#include<string>
#include<iterator>
#include <experimental/random>
#include<stack>
namespace InsertionSort {
template<typename Iterator>
void Sort_copy(Iterator begin, Iterator end) {
if (end - begin <= 1) return;
for (Iterator it = std::next(begin); it != end; ++it) {
Iterator aim = std::upper_bound(begin, it, *it);
auto temp = *it;
std::copy(aim, (it), std::next(aim));
*aim = temp;
}
}
}
namespace BubbleSort {
template<typename Iterator>
void Sort1(Iterator begin, Iterator end) {
auto len = std::distance(begin, end);
if (len <= 1) return;
bool flag(true);
while (flag) {
flag = false;
for (auto it(begin); it != std::prev(end); ++it) {
if ((*it) > (*std::next(it))) {
flag = true;
std::iter_swap(it, std::next(it));
}
}
}
}
}
namespace HeapSort {
template<typename Iterator>
void sift_down(Iterator begin, Iterator end, Iterator parent) {
auto size = std::distance(begin, end);
while (true) {
auto child = std::next(parent, std::distance(begin, parent) + 1);
if (std::distance(begin, child) >= size) break;
if (std::next(child, 1) < end && (*child) < (*std::next(child))) ++child;
if (*(child) > *(parent)) {
std::swap(*parent, *child);
parent = child;
} else break;
}
}
template<typename Iterator>
void Sort(Iterator begin, Iterator end) {
auto len = std::distance(begin, end);
for (auto i = (len - 1 - 1) / 2; i >= 0; --i) sift_down(begin, end, std::next(begin, i));
for (auto i = len - 1; i > 0; --i) {
std::iter_swap(begin, std::next(begin, i));
sift_down(begin, std::next(begin, i), begin);
}
}
}
namespace QuickSort {
template<typename T>
T randint(T lower, T upper) {
static std::random_device rd;
static std::mt19937 gen(rd());
std::uniform_int_distribution<T> dis(lower, upper);
return dis(gen);
}
template<typename Iterator>
std::vector<Iterator> PartitionThreeWaySTD(Iterator begin, Iterator end) {
using difference_type = typename std::iterator_traits<Iterator>::difference_type;
auto len = std::distance(begin, end);
auto pivot = *std::next(begin, randint((difference_type) 0, len - 1));
Iterator middle1 = std::partition(begin, end,
[&pivot](const auto &element) {
return (element < pivot);
});
Iterator middle2 = std::partition(middle1, end,
[&pivot](const auto &element) {
return (element <= pivot);
});
return {middle1, middle2};
}
template<typename Iterator>
void IntroSort(Iterator begin, Iterator end, int const depth, int const &insert_limit = 16) {
if (end <= begin) return;
if (end - begin + 1 < insert_limit) {
InsertionSort::Sort_copy(begin, end);
return;
}
if (!depth) {
HeapSort::Sort(begin, end);
}
auto pivot = PartitionThreeWaySTD(begin, end);
IntroSort(begin, pivot[0], depth - 1);
IntroSort(pivot[1], end, depth - 1);
}
template<typename Iterator>
void IntroSort(Iterator begin, Iterator end) {
int depth = static_cast<int>(2 * log(end - begin));
IntroSort(begin, end, depth);
}
}
void sort(unsigned *a, int n) {
QuickSort::IntroSort(a,a+n);
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 17.422 s | 512 MB + 48 KB | Accepted | Score: 100 | 显示更多 |