This documentation is automatically generated by competitive-verifier/competitive-verifier
#include "cp-algo/util/compress_coords.hpp"
#ifndef CP_ALGO_UTIL_COMPRESS_COORDS_HPP
#define CP_ALGO_UTIL_COMPRESS_COORDS_HPP
#include "sort.hpp"
#include <vector>
namespace cp_algo {
// coords is a range of reference_wrapper<T>
auto compress_coords(auto &&coords) {
using T = std::decay_t<std::unwrap_reference_t<
std::ranges::range_value_t<decltype(coords)>
>>;
std::vector<T> original;
if(empty(coords)) {
return original;
}
original.reserve(size(coords));
radix_sort(coords);
int idx = -1;
T prev = ~coords.front();
for(auto &x: coords) {
if(x != prev) {
idx++;
prev = x;
original.push_back(x);
}
x.get() = idx;
}
return original;
}
}
#endif // CP_ALGO_UTIL_COMPRESS_COORDS_HPP
#line 1 "cp-algo/util/compress_coords.hpp"
#line 1 "cp-algo/util/sort.hpp"
#line 1 "cp-algo/util/bit.hpp"
#include <immintrin.h>
#include <cstdint>
#include <array>
#include <bit>
namespace cp_algo {
template<typename Uint>
constexpr size_t bit_width = sizeof(Uint) * 8;
size_t order_of_bit(auto x, size_t k) {
return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
}
[[gnu::target("bmi2")]]
size_t kth_set_bit(uint64_t x, size_t k) {
return std::countr_zero(_pdep_u64(1ULL << k, x));
}
template<int fl = 0>
void with_bit_floor(size_t n, auto &&callback) {
if constexpr (fl >= 63) {
return;
} else if (n >> (fl + 1)) {
with_bit_floor<fl + 1>(n, callback);
} else {
callback.template operator()<1ULL << fl>();
}
}
}
#line 4 "cp-algo/util/sort.hpp"
#include <algorithm>
#include <numeric>
#include <ranges>
#include <vector>
namespace cp_algo {
template<size_t maxc>
void count_sort(auto &a, auto &&proj = std::identity{}) {
std::array<int, maxc> cnt = {};
for(auto &x: a) {
cnt[proj(x)]++;
}
std::partial_sum(begin(cnt), end(cnt), begin(cnt));
auto res = a;
for(auto const& it: a | std::views::reverse) {
res[--cnt[proj(it)]] = it;
}
a = std::move(res);
}
void radix_sort(auto &a) {
if(empty(a)) {
return;
}
auto [mn, mx] = std::ranges::minmax(a);
with_bit_floor<1>(size(a), [&]<size_t floor>() {
constexpr int base = std::min<size_t>(floor, 1 << 16);
for(int64_t i = 1; i <= mx - mn; i *= base) {
count_sort<base>(a, [&](auto x) {
return (x - mn) / i % base;
});
}
});
}
}
#line 5 "cp-algo/util/compress_coords.hpp"
namespace cp_algo {
// coords is a range of reference_wrapper<T>
auto compress_coords(auto &&coords) {
using T = std::decay_t<std::unwrap_reference_t<
std::ranges::range_value_t<decltype(coords)>
>>;
std::vector<T> original;
if(empty(coords)) {
return original;
}
original.reserve(size(coords));
radix_sort(coords);
int idx = -1;
T prev = ~coords.front();
for(auto &x: coords) {
if(x != prev) {
idx++;
prev = x;
original.push_back(x);
}
x.get() = idx;
}
return original;
}
}