Kodlo-chan
75 lines
3.5 KiB
C++
75 lines
3.5 KiB
C++
#include <cstdio>
|
|
#include <vector>
|
|
#include <random>
|
|
#include <chrono>
|
|
#include <algorithm>
|
|
#include "solution.cpp"
|
|
|
|
static int failures = 0;
|
|
#define CHECK(cond, name) do { if (cond) std::printf("ok %s\n", name); \
|
|
else { std::printf("FAIL %s (line %d)\n", name, __LINE__); ++failures; } } while (0)
|
|
|
|
static bool is_max_heap(const std::vector<int>& a) {
|
|
for (std::size_t i = 1; i < a.size(); ++i)
|
|
if (a[(i - 1) / 2] < a[i]) return false;
|
|
return true;
|
|
}
|
|
|
|
int main() {
|
|
{
|
|
std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
|
|
std::vector<int> before = a;
|
|
heapify(a);
|
|
CHECK(is_max_heap(a), "маленький массив: свойство max-heap держится");
|
|
std::vector<int> s1 = before, s2 = a;
|
|
std::sort(s1.begin(), s1.end()); std::sort(s2.begin(), s2.end());
|
|
CHECK(s1 == s2, "мультимножество сохранено");
|
|
std::vector<int> empty_a;
|
|
heapify(empty_a);
|
|
CHECK(empty_a.empty(), "пустой массив -> пустой");
|
|
std::vector<int> one = {7};
|
|
heapify(one);
|
|
CHECK(one.size() == 1 && one[0] == 7, "один элемент не теряется");
|
|
}
|
|
{
|
|
std::vector<int> a = {1, 2, 3, 4, 5};
|
|
CHECK(kth_largest(a, 1) == 5, "kth_largest k=1 -> максимум");
|
|
CHECK(kth_largest(a, 5) == 1, "kth_largest k=n -> минимум");
|
|
CHECK(kth_largest(a, 3) == 3, "kth_largest k=3 -> медиана");
|
|
std::vector<int> z = {4, 4, 4};
|
|
CHECK(kth_largest(z, 2) == 4, "дубликаты: k=2 -> 4");
|
|
std::vector<int> dup = {5, 5, 1, 1, 3};
|
|
CHECK(kth_largest(dup, 4) == 1, "дубликаты: k=4 -> 1");
|
|
std::vector<int> big = top_k(a, 3);
|
|
CHECK(big.size() == 3 && big[0] == 5 && big[1] == 4 && big[2] == 3, "top_k(3) по убыванию");
|
|
std::vector<int> all = top_k(a, 10);
|
|
CHECK(all.size() == 5 && all.front() == 5 && all.back() == 1, "top_k(k>n) -> все по убыванию");
|
|
std::vector<int> neg = {-5, -1, -9};
|
|
CHECK(kth_largest(neg, 1) == -1, "отрицательные: максимум -1");
|
|
CHECK(kth_largest(a, 100) == 1, "k>n не падает и даёт минимум");
|
|
}
|
|
{
|
|
const int N = 3000000;
|
|
std::mt19937 rng(777);
|
|
std::vector<int> a(N);
|
|
for (auto& x : a) x = int(rng() % 1000000);
|
|
std::vector<int> ref = a;
|
|
auto t0 = std::chrono::steady_clock::now();
|
|
heapify(a);
|
|
double sec = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
|
|
std::printf(" (3M heapify: time=%.3fs, top=%d)\n", sec, a.empty() ? -1 : a[0]);
|
|
CHECK(is_max_heap(a), "3M: свойство max-heap держится");
|
|
CHECK(a[0] == *std::max_element(ref.begin(), ref.end()), "3M: корень == максимум");
|
|
CHECK(sec < 2.0, "3M heapify за < 2 c");
|
|
t0 = std::chrono::steady_clock::now();
|
|
int k = kth_largest(ref, 1000);
|
|
double sec2 = std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count();
|
|
std::sort(ref.begin(), ref.end(), std::greater<int>());
|
|
std::printf(" (3M kth_largest k=1000: time=%.3fs, value=%d)\n", sec2, k);
|
|
CHECK(k == ref[999], "3M: kth_largest(k=1000) совпадает с сортировкой");
|
|
CHECK(sec2 < 3.0, "3M kth_largest за < 3 c");
|
|
}
|
|
std::printf(failures ? "\nFAILURES: %d\n" : "\nALL PASS\n", failures);
|
|
return failures ? 1 : 0;
|
|
}
|