2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
32#include <initializer_list>
46#include <unordered_map>
47#include <unordered_set>
54
55
56
57
62using u128 =
unsigned __int128;
66
67
69inline void throw_assertion_error(
const std::string &condition,
70 const std::string &msg,
const char *file,
72 throw std::runtime_error(
"tgen: " + msg +
" (assertion `" + condition +
73 "` failed at " + file +
":" +
74 std::to_string(line) +
")");
76inline void throw_assertion_error(
const std::string &condition,
77 const char *file,
int line) {
78 throw std::runtime_error(
"tgen: assertion `" + condition +
"` failed at " +
79 std::string(file) +
":" + std::to_string(line));
81inline std::runtime_error error(
const std::string &msg) {
82 return std::runtime_error(
"tgen: " + msg);
84inline std::runtime_error contradiction_error(
const std::string &type,
85 const std::string &msg =
"") {
87 std::string error_msg =
88 type +
": invalid " + type +
" (contradictory restrictions)";
90 error_msg +=
": " + msg;
91 return error(error_msg);
93inline std::runtime_error
94complex_restrictions_error(
const std::string &type,
95 const std::string &msg =
"") {
97 std::string error_msg =
98 type +
": cannot represent " + type +
" (complex restrictions)";
100 error_msg +=
": " + msg;
101 return error(error_msg);
103inline void tgen_ensure_against_bug(
bool cond,
const std::string &msg =
"") {
105 std::string error_msg;
107 error_msg =
"tgen: " + msg +
"\n";
108 error_msg +=
"tgen: THERE IS A BUG IN TGEN; PLEASE CONTACT MAINTAINERS";
109 throw std::runtime_error(error_msg);
114#define tgen_ensure(cond, ...)
116 tgen::detail::throw_assertion_error(#cond, ##__VA_ARGS__, __FILE__,
120inline bool registered =
false;
121inline void ensure_registered() {
123 "tgen was not registered! You should call "
124 "tgen::register_gen(argc, argv) before running tgen functions");
130template <
typename T,
typename =
void>
struct is_container : std::false_type {};
132struct is_container<T,
133 std::void_t<
typename std::remove_reference_t<T>::value_type,
134 decltype(std::begin(std::declval<T>())),
135 decltype(std::end(std::declval<T>()))>>
138template <
typename Char,
typename Traits,
typename Alloc>
139struct is_container<std::basic_string<Char, Traits, Alloc>> : std::false_type {
141template <
typename Char,
typename Traits,
typename Alloc>
142struct is_container<
const std::basic_string<Char, Traits, Alloc>>
143 : std::false_type {};
144template <
typename Char,
typename Traits,
typename Alloc>
145struct is_container<std::basic_string<Char, Traits, Alloc> &>
146 : std::false_type {};
147template <
typename Char,
typename Traits,
typename Alloc>
148struct is_container<
const std::basic_string<Char, Traits, Alloc> &>
149 : std::false_type {};
152template <
typename T>
struct is_pair : std::false_type {};
153template <
typename A,
typename B>
154struct is_pair<std::pair<A, B>> : std::true_type {};
156template <
typename T>
struct is_tuple : std::false_type {};
157template <
typename... Ts>
158struct is_tuple<std::tuple<Ts...>> : std::true_type {};
162 : std::bool_constant<!is_container<T>::value
and !is_tuple<T>::value
and
163 !is_pair<T>::value> {};
166struct is_container_multiline
167 : std::bool_constant<is_container<T>::value
and
168 !is_scalar<
typename std::remove_cv_t<
169 std::remove_reference_t<T>>::value_type>::value> {
172template <
typename T>
struct is_pair_multiline : std::false_type {};
173template <
typename A,
typename B>
174struct is_pair_multiline<std::pair<A, B>>
175 : std::bool_constant<!is_scalar<A>::value
or !is_scalar<B>::value> {};
177template <
typename Tuple>
struct is_tuple_multiline : std::false_type {};
178template <
typename... Ts>
179struct is_tuple_multiline<std::tuple<Ts...>>
180 : std::bool_constant<(!is_scalar<Ts>::value
or ...)> {};
183template <
typename>
inline constexpr bool dependent_false_v =
false;
186
187
190using is_sequential_tag =
void;
193template <
typename T,
typename =
void>
194struct is_associative_container : std::false_type {};
196struct is_associative_container<
197 T, std::void_t<
typename T::key_type,
typename T::key_compare>>
201template <
typename T,
typename =
void>
202struct is_sequential : std::false_type {};
205 T, std::void_t<
typename std::decay_t<T>::tgen_is_sequential_tag>>
209
210
213inline std::mt19937 rng;
216
217
222 bool IsCont = detail::is_container<std::decay_t<T>>::value>
223struct print_cols_view;
226template <
typename T>
struct print_cols_view<T,
true> {
228 decltype(std::begin(std::declval<
const T &>())) it;
230 print_cols_view(
const T &v) : value(v), it(v.begin()) {}
232 std::size_t size()
const {
return value.size(); }
233 decltype(
auto) get(std::size_t)
const {
return *it; }
234 void advance() { ++it; }
238template <
typename T>
struct print_cols_view<T,
false> {
241 print_cols_view(
const T &v) : value(v) {}
243 std::size_t size()
const {
return value.size(); }
244 decltype(
auto) get(std::size_t i)
const {
245 return value[
static_cast<
int>(i)];
251
252
256constexpr int distinct_attempt_multiplier = 84;
261template <
typename Seen,
typename Fn>
262auto try_generate_distinct(Seen &seen, Fn &&next,
bool insert =
true)
263 -> std::optional<std::invoke_result_t<Fn &>> {
264 using T = std::invoke_result_t<Fn &>;
266 distinct_attempt_multiplier * std::max<size_t>(1, seen.size());
267 for (size_t i = 0; i < attempts; ++i) {
270 if (seen.insert(val).second)
272 }
else if (seen.count(val) == 0)
281
282
285enum class compiler_kind { gcc, clang, unknown };
293 compiler_value(compiler_kind kind = compiler_kind::unknown,
int major = 0,
295 : kind_(kind), major_(major), minor_(minor) {}
304 cpp_value(std::optional<
int> version = std::nullopt)
305 : version_(version ? *version : 0) {
307 tgen_ensure(*version == 17
or *version == 20
or *version == 23,
308 "unsupported C++ version (use 17, 20, 23)");
319
320
323template <
typename T>
struct list;
326template <
typename Func,
typename... Args>
struct distinct {
328 std::tuple<Args...> args_;
333 : func_(std::move(func)), args_(std::move(args)...) {}
355 auto val = generate_distinct(
true);
359 throw detail::error(
"distinct: no more distinct values");
361 template <
typename U>
auto gen(std::initializer_list<U> il) {
362 return gen(std::vector<U>(il));
368 for (
int i = 0; i < size; ++i)
369 res.push_back(gen());
371 return typename list<T>::value(res);
377 bool empty() {
return generate_distinct(
false) == std::nullopt; }
383 auto val = generate_distinct(
true);
389 return typename list<T>::value(res);
393 friend std::ostream &operator<<(std::ostream &out,
const distinct &) {
395 detail::dependent_false_v<
distinct>,
396 "distinct: cannot print a distinct generator. Maybe you forgot to "
404 auto generate_distinct(
bool insert) {
405 return detail::try_generate_distinct(
406 seen_, [&] {
return std::apply(func_, args_); }, insert);
409template <
typename Func,
typename... Args>
410distinct(Func, Args...) ->
distinct<Func, Args...>;
414 const Gen &self()
const {
return *
static_cast<
const Gen *>(
this); }
416 template <
typename... Args>
auto gen_list(
int size, Args &&...args)
const {
417 std::vector<
typename Gen::value> res;
419 for (
int i = 0; i < size; ++i)
420 res.push_back(
static_cast<
const Gen *>(
this)->gen(
421 std::forward<Args>(args)...));
423 return typename list<
typename Gen::value>::value(res);
427 template <
typename Pred,
typename... Args>
428 auto gen_until(Pred predicate,
int max_tries, Args &&...args)
const {
429 for (
int i = 0; i < max_tries; ++i) {
430 typename Gen::value val =
static_cast<
const Gen *>(
this)->gen(
431 std::forward<Args>(args)...);
437 throw detail::error(
"could not generate value matching predicate");
439 template <
typename Pred,
typename T,
typename... Args>
440 auto gen_until(Pred predicate,
int max_tries, std::initializer_list<T> il,
441 Args &&...args)
const {
442 return gen_until(predicate, max_tries, std::vector<T>(il),
443 std::forward<Args>(args)...);
447 template <
typename... Args>
auto distinct(Args &&...args)
const {
449 [self = self()](
auto &&...inner_args)
mutable ->
decltype(
auto) {
451 std::forward<
decltype(inner_args)>(inner_args)...);
453 std::forward<Args>(args)...);
455 template <
typename T,
typename... Args>
456 auto distinct(std::initializer_list<T> il, Args &&...args)
const {
457 return distinct(std::vector<T>(il), std::forward<Args>(args)...);
461 friend std::ostream &operator<<(std::ostream &out,
const gen_base &) {
462 static_assert(detail::dependent_false_v<
gen_base>,
463 "gen_base: cannot print a generator. Maybe you forgot to "
471 const Val &self()
const {
return *
static_cast<
const Val *>(
this); }
474 return self().to_std() < rhs.to_std();
482struct is_generator_value
483 : std::is_base_of<gen_value_base<std::decay_t<T>>, std::decay_t<T>> {};
488
489
495 template <
typename T>
print(
const T &val,
char sep =
' ') {
496 std::ostringstream oss;
497 write(oss, val, sep);
500 template <
typename T>
501 print(
const std::initializer_list<T> &il,
char sep =
' ') {
502 std::ostringstream oss;
503 write(oss, std::vector<T>(il), sep);
506 template <
typename T>
507 print(
const std::initializer_list<std::initializer_list<T>> &il,
509 std::ostringstream oss;
510 std::vector<std::vector<T>> mat;
511 for (
const auto &i : il)
513 write(oss, mat, sep);
517 template <
typename T>
void write(std::ostream &os,
const T &val,
char sep) {
518 if constexpr (detail::is_pair<T>::value) {
519 if constexpr (detail::is_pair_multiline<T>::value) {
520 write(os, val.first, sep);
522 write(os, val.second, sep);
525 write(os, val.first,
' ');
527 write(os, val.second,
' ');
529 }
else if constexpr (detail::is_tuple<T>::value)
530 write_tuple(os, val, sep);
531 else if constexpr (detail::is_container<T>::value)
532 write_container(os, val, sep);
533 else if constexpr (std::is_same_v<T, detail::i128>
or
534 std::is_same_v<T, detail::u128>)
535 write_128_number(os, val);
541 template <
typename T>
void write_128_number(std::ostream &os, T num) {
542 static const long long BASE = 1e18;
548 detail::u128(0) -
static_cast<detail::u128>(num));
553 write_128_number(os, num / BASE);
554 os << std::setw(18) << std::setfill(
'0')
555 <<
static_cast<
long long>(num % BASE);
557 os <<
static_cast<
long long>(num);
560 template <
typename C>
561 void write_container(std::ostream &os,
const C &container,
char sep) {
564 for (
const auto &e : container) {
566 os << (detail::is_container_multiline<C>::value ?
'\n' : sep);
568 write(os, e, detail::is_container_multiline<C>::value ? sep :
' ');
573 template <
typename Tuple, size_t... I>
574 void write_tuple_impl(std::ostream &os,
const Tuple &tp,
char sep,
575 std::index_sequence<I...>) {
577 ((os << (first ? (first =
false,
"")
578 : (detail::is_tuple_multiline<Tuple>::value
580 : std::string(1, sep))),
581 write(os, std::get<I>(tp),
582 detail::is_tuple_multiline<Tuple>::value ? sep :
' ')),
585 template <
typename T>
586 void write_tuple(std::ostream &os,
const T &tp,
char sep) {
587 write_tuple_impl(os, tp, sep,
588 std::make_index_sequence<std::tuple_size<T>::value>{});
591 friend std::ostream &operator<<(std::ostream &out,
const print &pr) {
598 template <
typename T>
600 template <
typename T>
601 println(
const std::initializer_list<T> &il,
char sep =
' ')
603 template <
typename T>
604 println(
const std::initializer_list<std::initializer_list<T>> &il,
608 friend std::ostream &operator<<(std::ostream &out,
const println &pr) {
609 return out << pr.s_ <<
'\n';
627 ((detail::is_container<std::decay_t<Args>>::value
or
628 detail::is_sequential<std::decay_t<Args>>::value)
and
630 "print_cols: arguments must be containers or sequential generator "
632 std::ostringstream oss;
637 void write(std::ostream &os,
const Args &...args) {
638 auto views = std::apply(
639 [](
const Args &...inner_args) {
640 return std::make_tuple(
641 detail::print_cols_view<
decltype(inner_args)>{
644 std::forward_as_tuple(args...));
646 const std::size_t n = std::get<0>(views).size();
648 auto check = [&](
const auto &v) {
649 tgen_ensure(v.size() == n,
"print_cols: sizes should be the same");
651 std::apply([&](
const auto &...v) { (check(v), ...); }, views);
653 for (std::size_t i = 0; i < n; ++i) {
657 [&](
const auto &...v) {
658 ((os << (first ?
"" :
" ") <<
print(v.get(i)),
666 std::apply([](
auto &...v) { (v.advance(), ...); }, views);
670 friend std::ostream &operator<<(std::ostream &out,
const print_cols &pr) {
676
677
687using uniform_int_t = std::conditional_t<
688 (
sizeof(T) >=
sizeof(
short)), T,
689 std::conditional_t<std::is_signed_v<T>,
int,
unsigned int>>;
692template <
typename T>
void ensure_floating_range(T left, T right) {
694 std::isfinite(left)
and std::isfinite(right)
and left <= right
and
695 std::isfinite(right - left),
696 "floating range must have finite ordered endpoints and a finite width");
703template <
typename T> T
next(T right) {
704 detail::ensure_registered();
705 if constexpr (std::is_integral_v<T>) {
706 tgen_ensure(right >= 1,
"value for `next` must be valid");
707 return static_cast<T>(
708 std::uniform_int_distribution<detail::uniform_int_t<T>>(
710 static_cast<detail::uniform_int_t<T>>(right) - 1)(detail::rng));
711 }
else if constexpr (std::is_floating_point_v<T>) {
712 detail::ensure_floating_range(T(0), right);
713 return std::uniform_real_distribution<T>(0, right)(detail::rng);
715 throw detail::error(
"invalid type for next (" +
716 std::string(
typeid(T).name()) +
")");
724template <
typename T> T
next(T left, T right) {
725 detail::ensure_registered();
726 tgen_ensure(left <= right,
"range for `next` must be valid");
727 if constexpr (std::is_integral_v<T>)
728 return static_cast<T>(
729 std::uniform_int_distribution<detail::uniform_int_t<T>>(
730 static_cast<detail::uniform_int_t<T>>(left),
731 static_cast<detail::uniform_int_t<T>>(right))(detail::rng));
732 else if constexpr (std::is_floating_point_v<T>) {
733 detail::ensure_floating_range(left, right);
734 return std::uniform_real_distribution<T>(left, right)(detail::rng);
736 throw detail::error(
"invalid type for next (" +
737 std::string(
typeid(T).name()) +
")");
744T scale_skewed_integer(T left, T right,
double x,
bool half_open) {
746 if constexpr (
sizeof(T) <
sizeof(uint64_t)) {
747 long long lo = left, hi = right;
749 static_cast<
long long>(x *
static_cast<
double>(hi - lo));
750 return static_cast<T>(std::min(lo + offset, hi - half_open));
755 i128 lo = left, hi = right, span = hi - lo;
758 if (span <= (i128(1) << 62)) {
760 static_cast<
long long>(x *
static_cast<
double>(span));
761 offset = std::min(offset,
static_cast<
long long>(span) - half_open);
762 return static_cast<T>(lo + offset);
764 i128 offset =
static_cast<i128>(
static_cast<
long double>(x) *
765 static_cast<
long double>(span));
766 return static_cast<T>(std::min(lo + offset, hi - half_open));
794template <
typename T> T
wnext(T right,
int w) {
797 if (-5 <= w
and w <= 5) {
798 T val = next<T>(right);
799 for (
int i = 0; i < w; ++i)
800 val = std::max(val, next<T>(right));
801 for (
int i = 0; i < -w; ++i)
802 val = std::min(val, next<T>(right));
806 if constexpr (std::is_floating_point_v<T>)
807 detail::ensure_floating_range(T(0), right);
810 double x, r = next<
double>(0, 1);
813 x = std::pow(r, 1.0 / (
static_cast<
double>(w) + 1.0));
815 x = 1.0 - std::pow(r, 1.0 / (-
static_cast<
double>(w) + 1.0));
818 if constexpr (std::is_integral_v<T>) {
819 tgen_ensure(right >= 1,
"value for `wnext` must be valid");
820 return detail::scale_skewed_integer<T>(0, right, x,
true);
827template <
typename T> T
wnext(T left, T right,
int w) {
830 if (-5 <= w
and w <= 5) {
831 T val = next<T>(left, right);
832 for (
int i = 0; i < w; ++i)
833 val = std::max(val, next<T>(left, right));
834 for (
int i = 0; i < -w; ++i)
835 val = std::min(val, next<T>(left, right));
839 if constexpr (std::is_floating_point_v<T>)
840 detail::ensure_floating_range(left, right);
843 double x, r = next<
double>(0, 1);
846 x = std::pow(r, 1.0 / (
static_cast<
double>(w) + 1.0));
848 x = 1.0 - std::pow(r, 1.0 / (-
static_cast<
double>(w) + 1.0));
851 if constexpr (std::is_integral_v<T>) {
852 tgen_ensure(left <= right,
"range for `wnext` must be valid");
853 return detail::scale_skewed_integer(left, right, x,
false);
855 return left + T(x * (right - left));
862inline u128 next128(u128 total) {
863 tgen_ensure(total > 0,
"next128: total must be positive");
866 u128 limit = (u128(-1) / total) * total;
870 u128 r = (u128(next<uint64_t>(0, std::numeric_limits<uint64_t>::max()))
872 next<uint64_t>(0, std::numeric_limits<uint64_t>::max());
890 static_assert(std::is_arithmetic_v<T>,
891 "weighted_sampler requires an arithmetic weight type");
899 std::vector<storage_t> weight_;
900 std::vector<
int> alias_;
907 : n_(
static_cast<
int>(distribution.size())),
alias_(
n_) {
909 "weighted_sampler: distribution must be non-empty");
910 for (
const auto &w : distribution) {
912 "weighted_sampler: distribution must be non-negative");
913 if constexpr (std::is_floating_point_v<T>)
915 "weighted_sampler: weights must be finite");
918 total_ = std::accumulate(distribution.begin(), distribution.end(),
922 bool rescale =
false;
923 if constexpr (std::is_floating_point_v<T>) {
926 rescale = !std::isfinite(total_)
or
927 total_ < std::numeric_limits<
double>::min()
or
928 total_ > std::numeric_limits<
double>::max() / n_;
932 *std::max_element(distribution.begin(), distribution.end());
934 "weighted_sampler: total weight must be positive");
937 for (
const auto &w : distribution)
938 total_ +=
static_cast<
double>(w / scale);
943 "weighted_sampler: total weight must be positive");
945 std::queue<
int> big, small;
946 for (
int i = 0; i < n_; ++i) {
947 if constexpr (std::is_floating_point_v<T>)
948 weight_.push_back(storage_t(n_) *
949 storage_t(rescale ? distribution[i] / scale
952 weight_.push_back(storage_t(n_) * storage_t(distribution[i]));
953 if (weight_[i] < total_)
959 while (!small.empty()
and !big.empty()) {
960 int s = small.front();
967 weight_[b] -= total_ - weight_[s];
968 if (weight_[b] < total_)
974 if constexpr (std::is_integral_v<T>) {
975 detail::tgen_ensure_against_bug(
976 small.empty(),
"weighted_sampler: small must be empty");
979 while (!small.empty()) {
980 int i = small.front();
989 while (!big.empty()) {
992 if constexpr (std::is_integral_v<T>) {
993 detail::tgen_ensure_against_bug(
994 weight_[b] == total_,
995 "weighted_sampler: weight of big element must be total");
1000 weighted_sampler(
const std::initializer_list<T> &distribution)
1001 : weighted_sampler(std::vector<T>(distribution)) {}
1005 static detail::u128 sample_below(detail::u128 total) {
1006 return detail::next128(total);
1008 static double sample_below(
double total) {
1009 return tgen::next<
double>(0, total);
1016 int i = tgen::next<
int>(0, n_ - 1);
1017 return sample_below(total_) < weight_[i] ? i : alias_[i];
1020template <
typename T>
1022template <
typename T>
1027template <
typename T>
1031template <
typename T>
1032size_t next_by_distribution(
const std::initializer_list<T> &distribution) {
1033 return next_by_distribution(std::vector<T>(distribution));
1039template <
typename T>
1041 const std::vector<T> &distribution) {
1042 tgen_ensure(distribution.size() > 0,
"distribution must be non-empty");
1043 tgen_ensure(k >= 0,
"number of elements to choose must be non-negative");
1046 std::vector<
int> res;
1047 for (
int i = 0; i < k; ++i)
1048 res.push_back(
static_cast<
int>(am.next()));
1051template <
typename T>
1053many_by_distribution(
int k,
const std::initializer_list<T> &distribution) {
1054 return many_by_distribution(k, std::vector<T>(distribution));
1059template <
typename It>
void shuffle(It first, It last) {
1063 for (It i = first + 1; i != last; ++i)
1064 std::iter_swap(i, first + next(0,
static_cast<
int>(i - first)));
1069template <
typename C> [[nodiscard]]
auto shuffled(
const C &container) {
1070 if constexpr (detail::is_associative_container<C>::value) {
1071 std::vector<
typename C::value_type> vec(container.begin(),
1073 shuffle(vec.begin(), vec.end());
1076 auto new_container = container;
1077 shuffle(new_container.begin(), new_container.end());
1078 return new_container;
1081template <
typename T>
1082[[nodiscard]] std::vector<T> shuffled(
const std::initializer_list<T> &il) {
1083 return shuffled(std::vector<T>(il));
1089 int size =
static_cast<
int>(std::distance(first, last));
1090 tgen_ensure(size > 0,
"cannot pick from empty range");
1092 std::advance(it, next(0, size - 1));
1099 return pick(container.begin(), container.end());
1101template <
typename T> T pick(
const std::initializer_list<T> &il) {
1102 return pick(std::vector<T>(il));
1107template <
typename C,
typename T>
1109 std::vector<T> distribution) {
1110 tgen_ensure(container.size() == distribution.size(),
1111 "container and distribution must have the same size");
1112 auto it = container.begin();
1113 std::advance(it, next_by_distribution(distribution));
1116template <
typename C,
typename T>
1117typename C::value_type
1118pick_by_distribution(
const C &container,
1119 const std::initializer_list<T> &distribution) {
1120 return pick_by_distribution(container, std::vector<T>(distribution));
1122template <
typename T,
typename U>
1123T pick_by_distribution(
const std::initializer_list<T> &il,
1124 const std::vector<U> &distribution) {
1125 return pick_by_distribution(std::vector<T>(il), distribution);
1127template <
typename T,
typename U>
1128T pick_by_distribution(
const std::initializer_list<T> &il,
1129 const std::initializer_list<U> &distribution) {
1130 return pick_by_distribution(std::vector<T>(il),
1131 std::vector<U>(distribution));
1136template <
typename C> C
choose(
const C &container,
int k) {
1137 tgen_ensure(0 < k
and k <=
static_cast<
int>(container.size()),
1138 "number of elements to choose must be valid");
1139 std::vector<
typename C::value_type> new_vec;
1141 int need = k, left =
static_cast<
int>(container.size());
1142 for (
auto cur_it = container.begin(); cur_it != container.end(); ++cur_it) {
1143 if (next(1, left--) <= need) {
1144 new_container.insert(new_container.end(), *cur_it);
1148 return new_container;
1150template <
typename T>
1151std::vector<T> choose(
const std::initializer_list<T> &il,
int k) {
1152 return choose(std::vector<T>(il), k);
1165 count_type num_available_;
1167 std::unordered_map<index_type, index_type> virtual_list_;
1168 std::vector<T> pool_;
1169 bool uses_pool_ =
false;
1172 static constexpr size_t array_pool_max =
size_t{1} << 23;
1186 tgen_ensure(size() > 0,
"distinct_range: no more values to generate");
1189 size_t i = next<size_t>(pool_.size());
1190 T result = pool_[i];
1191 pool_[i] = pool_.back();
1197 index_type j =
static_cast<index_type>(size() - 1);
1198 index_type i = next<index_type>(0, j);
1200 auto vi_it = virtual_list_.find(i);
1201 index_type vi = vi_it == virtual_list_.end() ? i : vi_it->second;
1202 auto vj_it = virtual_list_.find(j);
1203 index_type vj = vj_it == virtual_list_.end() ? j : vj_it->second;
1204 virtual_list_[i] = vj;
1208 return value_at(vi);
1215 tgen_ensure(count >= 0,
"distinct_range: size must be nonnegative");
1216 tgen_ensure(
static_cast<count_type>(count) <= num_available_,
1217 "distinct_range: no more values to generate");
1220 return typename list<T>::value(std::vector<T>{});
1223 const size_t sample_count =
static_cast<size_t>(count);
1224 if (!uses_pool_
and num_available_ <= array_pool_max) {
1226 pool_.resize(
static_cast<size_t>(num_available_));
1227 if (virtual_list_.empty()) {
1229 const detail::i128 first = left_;
1230 for (size_t i = 0; i < pool_.size(); ++i)
1231 pool_[i] =
static_cast<T>(first + i);
1233 for (size_t i = 0; i < pool_.size(); ++i)
1235 value_at(mapped_index(
static_cast<index_type>(i)));
1237 virtual_list_.clear();
1242 auto pool = std::move(pool_);
1243 const size_t remaining = pool.size();
1245 for (size_t i = 0; i < sample_count; ++i) {
1246 size_t last = remaining - i - 1;
1247 size_t j = next<size_t>(0, last);
1248 std::swap(pool[j], pool[last]);
1250 res.assign(pool.end() - count, pool.end());
1251 pool.resize(remaining - sample_count);
1252 num_available_ -= sample_count;
1253 pool_ = std::move(pool);
1254 }
else if (count_type(sample_count) * 2 > num_available_) {
1255 res = sample_complement(sample_count);
1257 virtual_list_.reserve(virtual_list_.size() + sample_count * 2);
1258 res.reserve(sample_count);
1259 for (size_t i = 0; i < sample_count; ++i)
1260 res.push_back(
gen());
1262 return typename list<T>::value(std::move(res));
1269 tgen_ensure(size() <= std::numeric_limits<
int>::max(),
1270 "distinct_range: too many values for gen_all");
1271 return gen_list(
static_cast<
int>(size()));
1275 index_type mapped_index(index_type i)
const {
1276 auto it = virtual_list_.find(i);
1277 return it == virtual_list_.end() ? i : it->second;
1283 std::vector<T> sample_complement(size_t count) {
1284 const size_t remaining =
static_cast<size_t>(num_available_);
1285 const size_t excluded_count = remaining - count;
1286 std::unordered_set<index_type> excluded;
1287 excluded.reserve(excluded_count);
1289 for (size_t j = count; j < remaining; ++j) {
1290 index_type i = next<index_type>(0,
static_cast<index_type>(j));
1291 if (!excluded.insert(i).second)
1292 excluded.insert(
static_cast<index_type>(j));
1295 std::unordered_map<index_type, index_type> next_virtual;
1296 next_virtual.reserve(excluded_count);
1299 index_type slot = 0;
1300 for (size_t i = 0; i < remaining; ++i) {
1301 index_type index =
static_cast<index_type>(i);
1302 index_type mapped = mapped_index(index);
1303 if (excluded.count(index))
1304 next_virtual[slot++] = mapped;
1306 res.push_back(value_at(mapped));
1308 virtual_list_ = std::move(next_virtual);
1309 num_available_ = excluded_count;
1311 tgen::shuffle(res.begin(), res.end());
1317 count_type range_span()
const {
1321 return static_cast<count_type>(detail::i128(right_) - left_ + 1);
1324 T value_at(index_type index)
const {
1326 return static_cast<T>(detail::i128(left_) + index);
1332 std::vector<T> list_;
1333 distinct_range<size_t> idx_;
1336 template <
typename C>
1341 distinct_container(
const std::initializer_list<T> &il)
1342 : distinct_container(std::vector<T>(il)) {}
1349 T
gen() {
return list_[idx_.gen()]; }
1355 for (
int i = 0; i < size; ++i)
1356 res.push_back(
gen());
1357 return typename list<T>::value(res);
1365 res.push_back(
gen());
1366 return typename list<T>::value(res);
1369template <
typename C>
1373
1374
1375
1376
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1394
1395
1399 detail::cpp = detail::cpp_value(version);
1403
1404
1408 return {compiler_kind::gcc, major, minor};
1413 return {compiler_kind::clang, major, minor};
1418 detail::compiler.kind_ = compiler.kind_;
1419 detail::compiler.major_ = compiler.major_;
1420 detail::compiler.minor_ = compiler.minor_;
1427inline bool process_special_opt_flags(std::string &key) {
1429 if (key.find(
"tgen::CPP:") == 0) {
1430 size_t prefix_len = std::string(
"tgen::CPP:").size();
1432 std::isdigit(key[prefix_len])
and
1433 std::isdigit(key[prefix_len + 1]),
1434 "invalid CPP format");
1435 int version = std::stoi(key.substr(prefix_len, 2));
1443 size_t prefix_len = 0;
1445 if (key.find(
"tgen::GCC") == 0) {
1446 kind = compiler_kind::gcc;
1447 prefix_len = std::string(
"tgen::GCC").size();
1448 }
else if (key.find(
"tgen::CLANG") == 0) {
1449 kind = compiler_kind::clang;
1450 prefix_len = std::string(
"tgen::CLANG").size();
1455 if (key.size() == prefix_len) {
1460 tgen_ensure(key[prefix_len] ==
':',
"invalid compiler format");
1463 std::string inside = key.substr(prefix_len, key.size() - prefix_len);
1464 int major = 0, minor = 0;
1466 size_t dot = inside.find(
'.');
1467 if (dot == std::string::npos) {
1469 std::all_of(inside.begin(), inside.end(), ::isdigit),
1470 "invalid compiler version");
1471 major = std::stoi(inside);
1473 std::string maj = inside.substr(0, dot);
1474 std::string min = inside.substr(dot + 1);
1477 std::all_of(maj.begin(), maj.end(), ::isdigit)
and
1479 "invalid compiler major version");
1481 std::all_of(min.begin(), min.end(), ::isdigit)
and
1483 "invalid compiler minor version");
1485 major = std::stoi(maj);
1486 minor = std::stoi(min);
1494inline std::vector<std::string>
1496inline std::map<std::string, std::string>
1499template <
typename T> T get_opt(
const std::string &value) {
1501 size_t consumed = 0;
1502 if constexpr (std::is_same_v<T,
bool>) {
1503 if (value ==
"true" or value ==
"1")
1505 if (value ==
"false" or value ==
"0")
1507 }
else if constexpr (std::is_integral_v<T>) {
1508 if constexpr (std::is_unsigned_v<T>) {
1510 size_t first = value.find_first_not_of(
" \t\n\r\f\v");
1511 if (first != std::string::npos
and value[first] !=
'-') {
1512 auto parsed = std::stoull(value, &consumed);
1513 if (consumed == value.size()
and
1514 parsed <= std::numeric_limits<T>::max())
1515 return static_cast<T>(parsed);
1518 auto parsed = std::stoll(value, &consumed);
1519 if (consumed == value.size()
and
1520 std::numeric_limits<T>::min() <= parsed
and
1521 parsed <= std::numeric_limits<T>::max())
1522 return static_cast<T>(parsed);
1524 }
else if constexpr (std::is_floating_point_v<T>) {
1528 int saved_errno = errno;
1530 auto parsed = std::strtold(value.c_str(), &end);
1531 int parse_error = errno;
1532 errno = saved_errno;
1535 (parse_error == ERANGE
and parsed != 0
and
1536 std::abs(parsed) < std::numeric_limits<
long double>::min());
1539 if (end != value.c_str()
and end == value.c_str() + value.size()
and
1541 (!std::isfinite(parsed)
or
1542 (std::numeric_limits<T>::lowest() <= parsed
and
1543 parsed <= std::numeric_limits<T>::max()))) {
1544 T result =
static_cast<T>(parsed);
1545 if (parsed == 0
or result != 0)
1553 throw error(
"invalid value `" + value +
"` for type " +
typeid(T).name());
1556inline void parse_opts(
int argc,
char **argv) {
1559 for (
int i = 1; i < argc; ++i) {
1560 std::string key(argv[i]);
1562 if (process_special_opt_flags(key))
1565 if (key[0] ==
'-') {
1567 "invalid opt (" + std::string(argv[i]) +
")");
1568 if (
'0' <= key[1]
and key[1] <=
'9') {
1570 pos_opts.push_back(key);
1575 key = key.substr(1);
1578 pos_opts.push_back(key);
1583 if (key[0] ==
'-') {
1585 "invalid opt (" + std::string(argv[i]) +
")");
1588 key = key.substr(1);
1595 std::size_t eq = key.find(
'=');
1596 if (eq != std::string::npos) {
1598 std::string value = key.substr(eq + 1);
1599 key = key.substr(0, eq);
1601 "expected non-empty key/value in opt (" +
1602 std::string(argv[i]) +
")");
1604 "cannot have repeated keys");
1605 named_opts[key] = value;
1609 "cannot have repeated keys");
1610 tgen_ensure(argv[i + 1],
"value cannot be empty");
1611 named_opts[key] = std::string(argv[i + 1]);
1617inline void set_seed(
int argc,
char **argv) {
1618 std::vector<uint32_t> seed;
1621 for (
int i = 1; i < argc; ++i) {
1623 size_t size_pos = seed.size();
1625 for (
char *s = argv[i]; *s !=
'\0'; ++s) {
1630 std::seed_seq seq(seed.begin(), seed.end());
1638 detail::ensure_registered();
1639 return index < detail::pos_opts.size();
1644 detail::ensure_registered();
1645 return detail::named_opts.count(key) != 0;
1647template <
typename K>
1648std::enable_if_t<std::is_same_v<K,
char>,
bool> has_opt(K key) {
1654template <
typename T>
1655T
opt(size_t index, std::optional<T> default_value = std::nullopt) {
1656 detail::ensure_registered();
1657 if (!has_opt(index)) {
1659 return *default_value;
1660 throw detail::error(
"cannot find opt at index " +
1661 std::to_string(index));
1663 return detail::get_opt<T>(detail::pos_opts[index]);
1668template <
typename T>
1669T
opt(
const std::string &key, std::optional<T> default_value = std::nullopt) {
1670 detail::ensure_registered();
1673 return *default_value;
1674 throw detail::error(
"cannot find opt with key " + key);
1676 return detail::get_opt<T>(detail::named_opts[key]);
1678template <
typename T,
typename K>
1679std::enable_if_t<std::is_same_v<K,
char>, T>
1680opt(K key, std::optional<T> default_value = std::nullopt) {
1681 return opt<T>(std::string(1, key), default_value);
1686 detail::set_seed(argc, argv);
1688 detail::pos_opts.clear();
1689 detail::named_opts.clear();
1690 detail::parse_opts(argc, argv);
1692 detail::registered =
true;
1698 detail::rng.seed(*seed);
1702 detail::pos_opts.clear();
1703 detail::named_opts.clear();
1705 detail::registered =
true;
1709
1710
1711
1712
1715
1716
1717
1718
1726 range_type value_l_, value_r_;
1727 std::set<T> values_;
1732 mutable std::vector<std::pair<range_type, range_type>>
1734 mutable std::vector<std::vector<
int>> neigh_;
1735 std::vector<std::set<
int>>
1737 bool index_constraints_{
1739 mutable bool uses_full_range_{
1744 list(
int size, T value_left, T value_right)
1746 uses_full_range_(
true) {
1747 tgen_ensure(size_ > 0,
"list: size must be positive");
1748 tgen_ensure(value_l_ <= value_r_,
"list: value range must be valid");
1754 tgen_ensure(size_ > 0,
"list: size must be positive");
1755 tgen_ensure(!values.empty(),
"list: value set must be non-empty");
1756 value_l_ = 0, value_r_ =
static_cast<range_type>(values.size() - 1);
1757 val_range_.assign(size_, {value_l_, value_r_});
1759 for (T val : values_)
1760 value_idx_in_set_[val] = idx++;
1765 tgen_ensure(0 <= idx
and idx < size_,
"list: index must be valid");
1766 ensure_val_range_materialized();
1767 if (values_.size() == 0) {
1768 auto &[left, right] = val_range_[idx];
1769 if (left == right
and value_l_ != value_r_) {
1771 "list: must not set to two different values");
1774 "list: value must be in the defined range");
1779 "list: value must be in the set of values");
1780 auto &[left, right] = val_range_[idx];
1781 range_type new_val =
1782 static_cast<range_type>(value_idx_in_set_[val]);
1784 "list: must not set to two different values");
1785 left = right = new_val;
1787 index_constraints_ =
true;
1794 std::max(idx_1, idx_2) < size_,
1795 "list: indices must be valid");
1799 ensure_val_range_materialized();
1800 ensure_neigh_allocated();
1801 index_constraints_ =
true;
1802 neigh_[idx_1].push_back(idx_2);
1803 neigh_[idx_2].push_back(idx_1);
1809 if (!indices.empty()) {
1810 tgen_ensure(0 <= *indices.begin()
and *indices.rbegin() < size_,
1811 "list: indices must be valid");
1812 std::set<
int>::iterator beg = indices.begin();
1813 for (
auto it = std::next(beg); it != indices.end(); ++it)
1821 tgen_ensure(0 <= left
and left <= right
and right < size_,
1822 "list: range indices must be valid");
1823 for (
int i = left; i < right; ++i)
1835 if (!indices.empty()) {
1836 tgen_ensure(0 <= *indices.begin()
and *indices.rbegin() < size_,
1837 "list: indices must be valid");
1838 diff_restrictions_.push_back(indices);
1845 std::set<
int> indices = {idx_1, idx_2};
1851 tgen_ensure(0 <= left
and left <= right
and right < size_,
1852 "list: range indices must be valid");
1853 std::vector<
int> indices(right - left + 1);
1854 std::iota(indices.begin(), indices.end(), left);
1855 return different(std::set<
int>(indices.begin(), indices.end()));
1860 std::vector<
int> indices(size_);
1861 std::iota(indices.begin(), indices.end(), 0);
1862 return different(std::set<
int>(indices.begin(), indices.end()));
1867 for (
int i = 1; i < size_; ++i)
1875 using tgen_is_sequential_tag = detail::is_sequential_tag;
1877 using value_type = T;
1880 std::vector<T> vec_;
1884 value(std::vector<T> &&vec) : vec_(std::move(vec)), sep_(
' ') {}
1885 value(
const std::initializer_list<T> &il) : value(std::vector<T>(il)) {}
1888 int size()
const {
return static_cast<
int>(vec_.size()); }
1893 "list: value: index out of bounds");
1896 const T &operator[](
int idx)
const {
1898 "list: value: index out of bounds");
1905 std::sort(vec_.begin(), vec_.end());
1912 std::reverse(vec_.begin(), vec_.end());
1926 std::vector<T> new_vec = vec_;
1927 for (
int i = 0; i < rhs
.size(); ++i)
1928 new_vec.push_back(rhs[i]);
1929 return value(new_vec);
1935 tgen::shuffle(vec_.begin(), vec_.end());
1941 T
pick()
const {
return vec_[next<
int>(0, size() - 1)]; }
1945 template <
typename Dist>
1948 "value and distribution must have the same size");
1949 return vec_[next_by_distribution(distribution)];
1951 template <
typename Dist>
1952 T pick_by_distribution(
1953 const std::initializer_list<Dist> &distribution)
const {
1954 return pick_by_distribution(std::vector<Dist>(distribution));
1961 "number of elements to choose must be valid");
1962 std::vector<T> new_vec;
1964 for (
int i = 0; need > 0; ++i) {
1966 if (next(1, left) <= need) {
1967 new_vec.push_back(vec_[i]);
1971 return value(new_vec);
1975 friend std::ostream &operator<<(std::ostream &out,
const value &val) {
1976 for (
int i = 0; i < val.size(); ++i) {
1986 if constexpr (!detail::is_generator_value<T>::value) {
1989 std::vector<
typename T::std_type> vec;
1990 for (
const auto &i : vec_)
1991 vec.push_back(i.to_std());
2001 if (diff_restrictions_.empty()) {
2002 if (
auto unconstrained = try_gen_unconstrained())
2003 return *unconstrained;
2005 if (
auto all_different = try_gen_all_different())
2006 return *all_different;
2008 ensure_neigh_allocated();
2009 std::vector<range_type> vec(size_);
2010 std::vector<
bool> defined_idx(
2013 std::vector<
int> comp_id(size_, -1);
2014 std::vector<std::vector<
int>> comp(size_);
2018 auto define_comp = [&](
int cur_comp, range_type val) {
2019 for (
int idx : comp[cur_comp]) {
2022 defined_idx[idx] =
true;
2028 std::vector<
bool> vis(size_,
false);
2029 for (
int idx = 0; idx < size_; ++idx)
2031 range_type new_value;
2032 bool value_defined =
false;
2036 std::queue<
int> q({idx});
2038 std::vector<
int> component;
2039 while (!q.empty()) {
2040 int cur_idx = q.front();
2043 component.push_back(cur_idx);
2046 auto [l, r] = val_range_at(cur_idx);
2048 if (!value_defined) {
2050 value_defined =
true;
2052 }
else if (new_value != l) {
2054 throw detail::contradiction_error(
2056 "tried to set value to `" +
2057 std::to_string(new_value) +
2058 "`, but it was already set as `" +
2059 std::to_string(l) +
"`");
2063 for (
int nxt_idx : neigh_[cur_idx]) {
2064 if (!vis[nxt_idx]) {
2065 vis[nxt_idx] =
true;
2072 for (
int cur_idx : component) {
2073 comp_id[cur_idx] = comp_count;
2074 comp[comp_id[cur_idx]].push_back(cur_idx);
2079 define_comp(comp_count, new_value);
2086 std::vector<std::set<
int>> diff_containing_comp_idx(comp_count);
2089 for (
const std::set<
int> &diff : diff_restrictions_) {
2091 if (detail::i128(diff.size()) > range_cardinality())
2092 throw detail::contradiction_error(
2094 "tried to generate " + std::to_string(diff.size()) +
2095 " different values, but the maximum is " +
2097 static_cast<uint64_t>(range_cardinality())));
2101 std::set<
int> comp_ids;
2102 for (
int idx : diff) {
2103 if (comp_ids.count(comp_id[idx]))
2104 throw detail::contradiction_error(
2105 "list",
"tried to set two indices as equal and "
2107 comp_ids.insert(comp_id[idx]);
2109 diff_containing_comp_idx[comp_id[idx]].insert(dist_id);
2116 for (
auto &diff_containing : diff_containing_comp_idx)
2117 if (diff_containing.size() >= 3)
2118 throw detail::complex_restrictions_error(
2120 "one index cannot be in >= 3 'different' restrictions");
2122 std::vector<
bool> vis_diff(diff_restrictions_.size(),
false);
2123 std::vector<
bool> initially_defined_comp_idx(comp_count,
false);
2126 auto define_tree = [&](
int diff_id) {
2131 std::set<range_type> defined_values;
2132 for (
int idx : diff_restrictions_[diff_id])
2133 if (defined_idx[idx]) {
2136 if (defined_values.count(vec[idx]))
2137 throw detail::contradiction_error(
2139 "tried to set two indices as equal and different");
2141 defined_values.insert(vec[idx]);
2146 int new_value_count =
2147 static_cast<
int>(diff_restrictions_[diff_id].size()) -
2148 static_cast<
int>(defined_values.size());
2149 std::vector<range_type> generated_values =
2150 generate_distinct_values(new_value_count, defined_values);
2151 auto val_it = generated_values.begin();
2152 for (
int idx : diff_restrictions_[diff_id])
2153 if (defined_idx[idx]) {
2156 initially_defined_comp_idx[comp_id[idx]] =
false;
2158 define_comp(comp_id[idx], *val_it);
2164 std::queue<std::pair<
int,
int>> q;
2165 q.emplace(diff_id, -1);
2166 vis_diff[diff_id] =
true;
2167 while (!q.empty()) {
2168 auto [cur_diff, parent] = q.front();
2171 std::set<
int> neigh_diff;
2172 for (
int idx : diff_restrictions_[cur_diff])
2174 diff_containing_comp_idx[comp_id[idx]]) {
2175 if (nxt_diff == cur_diff
or nxt_diff == parent)
2179 if (vis_diff[nxt_diff])
2180 throw detail::complex_restrictions_error(
2182 "cycle found in 'different' restrictions");
2184 neigh_diff.insert(nxt_diff);
2187 for (
int nxt_diff : neigh_diff) {
2188 vis_diff[nxt_diff] =
true;
2189 q.emplace(nxt_diff, cur_diff);
2192 std::set<range_type> nxt_defined_values;
2193 for (
int idx2 : diff_restrictions_[nxt_diff])
2194 if (defined_idx[idx2]) {
2198 if (initially_defined_comp_idx[comp_id[idx2]])
2199 throw detail::complex_restrictions_error(
2202 nxt_defined_values.insert(vec[idx2]);
2204 int new_value_count =
2205 static_cast<
int>(diff_restrictions_[nxt_diff].size()) -
2206 static_cast<
int>(nxt_defined_values.size());
2207 std::vector<range_type> generated_values =
2208 generate_distinct_values(new_value_count,
2209 nxt_defined_values);
2210 auto val_it = generated_values.begin();
2211 for (
int idx2 : diff_restrictions_[nxt_diff])
2212 if (!defined_idx[idx2]) {
2213 define_comp(comp_id[idx2], *val_it);
2225 std::vector<std::pair<
int,
int>> defined_cnt_and_diff_idx;
2227 for (
const std::set<
int> &diff : diff_restrictions_) {
2228 int defined_cnt = 0;
2229 for (
int idx : diff)
2230 if (defined_idx[idx]) {
2232 initially_defined_comp_idx[comp_id[idx]] =
true;
2234 defined_cnt_and_diff_idx.emplace_back(defined_cnt, dist_id);
2238 std::sort(defined_cnt_and_diff_idx.rbegin(),
2239 defined_cnt_and_diff_idx.rend());
2240 for (
auto [defined_cnt, diff_idx] : defined_cnt_and_diff_idx)
2241 if (!vis_diff[diff_idx])
2242 define_tree(diff_idx);
2246 for (std::size_t dist_id = 0; dist_id < diff_restrictions_.size();
2248 if (!vis_diff[dist_id])
2249 define_tree(
static_cast<
int>(dist_id));
2255 for (
int idx = 0; idx < size_; ++idx)
2256 if (!defined_idx[idx])
2257 define_comp(comp_id[idx], next<range_type>(value_l_, value_r_));
2259 if (!values_.empty()) {
2261 std::vector<range_type> value_vec(values_.begin(), values_.end());
2262 for (range_type &val : vec)
2263 val = value_vec[val];
2266 if constexpr (std::is_same_v<range_type, T>)
2267 return value(std::move(vec));
2269 return value(std::vector<T>(vec.begin(), vec.end()));
2273 detail::i128 range_cardinality()
const {
2275 return detail::i128(value_r_) - detail::i128(value_l_) + 1;
2278 void ensure_neigh_allocated()
const {
2279 if (neigh_.size() ==
static_cast<size_t>(size_))
2281 neigh_.assign(size_, {});
2285 void ensure_val_range_materialized()
const {
2286 if (!uses_full_range_)
2288 val_range_.assign(size_, {value_l_, value_r_});
2289 uses_full_range_ =
false;
2293 std::pair<range_type, range_type> val_range_at(
int idx)
const {
2294 if (uses_full_range_)
2295 return {value_l_, value_r_};
2296 return val_range_[idx];
2301 std::vector<range_type> generate_distinct_values(
2302 int k,
const std::set<range_type> &forbidden_values)
const {
2303 for (
auto forbidden : forbidden_values)
2304 tgen_ensure(value_l_ <= forbidden
and forbidden <= value_r_);
2305 const detail::i128 available =
2306 range_cardinality() - forbidden_values.size();
2308 throw detail::complex_restrictions_error(
2309 "list",
"not enough distinct values");
2312 if (forbidden_values.empty())
2313 return distinct_range<range_type>(value_l_, value_r_)
2320 const uint64_t count =
static_cast<uint64_t>(available);
2321 std::map<uint64_t, uint64_t> virtual_list;
2322 std::vector<std::pair<uint64_t,
int>> ranks;
2323 ranks.reserve(
static_cast<size_t>(k));
2324 for (
int i = 0; i < k; ++i) {
2325 uint64_t index =
static_cast<uint64_t>(i);
2326 uint64_t j = next<uint64_t>(index, count - 1);
2327 uint64_t vj = virtual_list.count(j) ? virtual_list[j] : j;
2329 virtual_list.count(index) ? virtual_list[index] : index;
2330 virtual_list[j] = vi;
2331 ranks.emplace_back(vj, i);
2334 std::sort(ranks.begin(), ranks.end());
2335 std::vector<range_type> result(
static_cast<size_t>(k));
2336 auto forbidden = forbidden_values.begin();
2337 detail::i128 skipped = 0;
2338 for (
auto [rank, index] : ranks) {
2340 detail::i128 chosen = detail::i128(value_l_) + rank + skipped;
2341 while (forbidden != forbidden_values.end()
and
2342 *forbidden <= chosen) {
2347 result[index] =
static_cast<range_type>(chosen);
2355 std::optional<
value> try_gen_unconstrained()
const {
2356 if (!values_.empty()
or index_constraints_)
2357 return std::nullopt;
2359 std::vector<T> vec(size_);
2360 for (
int i = 0; i < size_; ++i)
2362 next<T>(
static_cast<T>(value_l_),
static_cast<T>(value_r_));
2370 std::optional<
value> try_gen_all_different()
const {
2371 if (!values_.empty()
or diff_restrictions_.size() != 1)
2372 return std::nullopt;
2374 const std::set<
int> &diff = diff_restrictions_[0];
2375 if (
static_cast<
int>(diff.size()) != size_
or *diff.begin() != 0
or
2376 *diff.rbegin() != size_ - 1)
2377 return std::nullopt;
2379 if (!neigh_.empty()) {
2380 for (
const auto &adj : neigh_) {
2382 return std::nullopt;
2386 if (index_constraints_)
2387 return std::nullopt;
2389 if (detail::i128(size_) > range_cardinality())
2390 throw detail::contradiction_error(
2392 "tried to generate " + std::to_string(size_) +
2393 " different values, but the maximum is " +
2394 std::to_string(
static_cast<uint64_t>(range_cardinality())));
2396 return distinct_range<T>(
static_cast<T>(value_l_),
2397 static_cast<T>(value_r_))
2403
2404
2405
2406
2409
2410
2411
2412
2416 std::vector<std::pair<
int,
int>> defs_;
2417 std::optional<std::vector<
int>> cycle_sizes_;
2421 tgen_ensure(size_ > 0,
"permutation: size must be positive");
2427 "permutation: index must be valid");
2428 defs_.emplace_back(idx, val);
2436 int remaining = size_;
2437 for (
int cycle_size : cycle_sizes) {
2439 "permutation: cycle sizes must be positive");
2441 cycle_size <= remaining,
2442 "permutation: cycle sizes must add up to size of permutation");
2443 remaining -= cycle_size;
2447 "permutation: cycle sizes must add up to size of permutation");
2448 cycle_sizes_ = cycle_sizes;
2451 permutation &cycles(
const std::initializer_list<
int> &cycle_sizes) {
2452 return cycles(std::vector<
int>(cycle_sizes));
2458 using tgen_is_sequential_tag = detail::is_sequential_tag;
2461 std::vector<
int> vec_;
2463 bool print_1_based_;
2466 :
vec_(
vec), sep_(
' '), print_1_based_(
false) {
2467 tgen_ensure(!vec_.empty(),
"permutation: value: cannot be empty");
2468 std::vector<
bool> vis(vec_.size(),
false);
2469 for (
int i = 0; i <
size(); ++i) {
2471 vec_[i] <
static_cast<
int>(vec_.size()),
2472 "permutation: value: values must be from `0` to "
2475 "permutation: value: cannot have repeated values");
2476 vis[vec_[i]] =
true;
2479 value(
const std::initializer_list<
int> &il)
2480 : value(std::vector<
int>(il)) {}
2483 int size()
const {
return static_cast<
int>(vec_.size()); }
2488 "permutation: value: index out of bounds");
2495 std::vector<
bool> vis(
size(),
false);
2498 for (
int i = 0; i <
size(); ++i)
2501 for (
int j = i; !vis[j]; j = vec_[j])
2505 return ((
size() - cycles) % 2 == 0) ? +1 : -1;
2511 for (
int i = 0; i < size(); ++i)
2519 std::reverse(vec_.begin(), vec_.end());
2526 std::vector<
int> inv(
size());
2527 for (
int i = 0; i < size(); ++i)
2544 print_1_based_ =
true;
2551 tgen::shuffle(vec_.begin(), vec_.end());
2557 int pick()
const {
return vec_[next<
int>(0, size() - 1)]; }
2561 template <
typename Dist>
2564 "value and distribution must have the same size");
2565 return vec_[next_by_distribution(distribution)];
2567 template <
typename Dist>
2568 int pick_by_distribution(
2569 const std::initializer_list<Dist> &distribution)
const {
2570 return pick_by_distribution(std::vector<Dist>(distribution));
2574 friend std::ostream &operator<<(std::ostream &out,
const value &val) {
2575 for (
int i = 0; i < val
.size(); ++i) {
2578 out << val
[i
] + val.print_1_based_;
2590 std::vector<
int> out = vec_;
2602 !cycle_sizes_
or defs_.empty(),
2603 "permutation: fixed values and cycle sizes cannot be combined");
2604 if (!cycle_sizes_) {
2606 std::vector<
int> idx_to_val(size_, -1), val_to_idx(size_, -1);
2607 for (
auto [idx, val] : defs_) {
2609 0 <= val
and val < size_,
2610 "permutation: value in permutation must be in [0, " +
2611 std::to_string(size_) +
")");
2613 if (idx_to_val[idx] != -1) {
2615 "permutation: cannot set an index to two "
2616 "different values");
2618 idx_to_val[idx] = val;
2620 if (val_to_idx[val] != -1) {
2622 "permutation: cannot set two indices to the "
2625 val_to_idx[val] = idx;
2628 std::vector<
int> perm(size_);
2629 std::iota(perm.begin(), perm.end(), 0);
2630 shuffle(perm.begin(), perm.end());
2632 for (
int &i : idx_to_val)
2635 while (val_to_idx[perm[cur_idx]] != -1)
2637 i = perm[cur_idx++];
2643 std::vector<
int> order(size_);
2644 std::iota(order.begin(), order.end(), 0);
2645 shuffle(order.begin(), order.end());
2647 std::vector<std::vector<
int>> cycles;
2648 for (
int cycle_size : *cycle_sizes_) {
2649 cycles.emplace_back();
2650 for (
int i = 0; i < cycle_size; ++i)
2651 cycles.back().push_back(order[idx++]);
2655 std::vector<
int> perm(size_, -1);
2656 for (
const std::vector<
int> &cycle : cycles) {
2657 int cur_size =
static_cast<
int>(cycle.size());
2658 for (
int i = 0; i < cur_size; ++i)
2659 perm[cycle[i]] = cycle[(i + 1) % cur_size];
2667
2668
2669
2670
2676using namespace tgen::detail;
2678inline int popcount(uint64_t x) {
return __builtin_popcountll(x); }
2680inline int ctzll(uint64_t x) {
2683 static const unsigned char index64[64] = {
2684 0, 1, 2, 53, 3, 7, 54, 27, 4, 38, 41, 8, 34, 55, 48, 28,
2685 62, 5, 39, 46, 44, 42, 22, 9, 24, 35, 59, 56, 49, 18, 29, 11,
2686 63, 52, 6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
2687 51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12};
2688 return index64[((x & -x) * 0x022FDD63CC95386D) >> 58];
2691inline uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
2692 return static_cast<uint64_t>(
static_cast<u128>(a) * b % m);
2697inline uint64_t expo_mod(uint64_t x, uint64_t y, uint64_t m) {
2700 uint64_t ans = expo_mod(mul_mod(x, x, m), y / 2, m);
2701 return y % 2 ? mul_mod(x, ans, m) : ans;
2710 if (n == 2
or n == 3)
2715 uint64_t r = detail::ctzll(n - 1), d = n >> r;
2717 for (
int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
2718 uint64_t x = detail::expo_mod(a, d, n);
2719 if (x == 1
or x == n - 1
or a % n == 0)
2722 for (uint64_t j = 0; j < r - 1; ++j) {
2723 x = detail::mul_mod(x, x, n);
2735inline uint64_t pollard_rho(uint64_t n) {
2738 auto f = [n](uint64_t x) {
return mul_mod(x, x, n) + 1; };
2740 uint64_t x = 0, y = 0, t = 30, prd = 2, x0 = 1, q;
2741 while (t % 40 != 0
or std::gcd(prd, n) == 1) {
2744 q = mul_mod(prd, x > y ? x - y : y - x, n);
2747 x = f(x), y = f(f(y)), ++t;
2749 return std::gcd(prd, n);
2752inline std::vector<uint64_t> factor(uint64_t n) {
2757 uint64_t d = pollard_rho(n);
2758 std::vector<uint64_t> l = factor(d), r = factor(n / d);
2759 l.insert(l.end(), r.begin(), r.end());
2764template <
typename T>
2765std::runtime_error there_is_no_in_range_error(
const std::string &type, T l,
2767 return error(
"math: there is no " + type +
" in range [" +
2768 std::to_string(l) +
", " + std::to_string(r) +
"]");
2770template <
typename T>
2771std::runtime_error there_is_no_from_error(
const std::string &type, T r) {
2772 return error(
"math: there is no " + type +
" from " + std::to_string(r));
2774template <
typename T>
2775std::runtime_error there_is_no_upto_error(
const std::string &type, T r) {
2776 return error(
"math: there is no " + type +
" up to " + std::to_string(r));
2782inline i128 modular_inverse_128(i128 a, i128 mod) {
2784 "math: modular inverse requires 0 < value < mod");
2786 i128 t = 0, new_t = 1;
2787 i128 r = mod, new_r = a;
2789 while (new_r != 0) {
2792 auto tmp_t = t - q * new_t;
2796 auto tmp_r = r - q * new_r;
2801 tgen_ensure(r == 1,
"math: remainder and mod must be coprime");
2809inline bool mul_leq(uint64_t a, uint64_t b, uint64_t limit) {
2810 if (a == 0
or b == 0)
2812 return a <= limit / b;
2816inline std::optional<uint64_t> expo(uint64_t base, uint64_t exp,
2818 uint64_t result = 1;
2822 if (!mul_leq(result, base, limit))
2823 return std::nullopt;
2832 if (!mul_leq(base, base, limit))
2833 return std::nullopt;
2841inline uint64_t kth_root_floor(uint64_t n, uint64_t k) {
2842 tgen_ensure_against_bug(k > 0,
"math: value must be valid");
2843 if (k == 1
or n <= 1)
2846 uint64_t lo = 1, hi = 1ULL << ((64 + k - 1) / k);
2849 uint64_t mid = lo + (hi - lo + 1) / 2;
2851 if (expo(mid, k, n)) {
2862inline i128 gcd128(i128 a, i128 b) {
2878inline i128 mul_saturate(i128 a, i128 b) {
2880 static const i128 LIMIT =
static_cast<i128>(1) << 64;
2881 if (a == 0
or b == 0)
2892 crt() : a(0), m(1) {}
2893 crt(T a_, T m_) : a(a_), m(m_) {}
2894 crt operator*(crt C) {
2895 if (m == 0
or C.m == 0)
2898 T g = gcd128(m, C.m);
2899 if ((C.a - a) % g != 0)
2908 T inv = modular_inverse_128(m1 % m2, m2);
2910 T k = ((C.a - a) / g) % m2;
2914 k =
static_cast<u128>(k) * inv % m2;
2916 T lcm = mul_saturate(m, m2);
2918 T res = (a +
static_cast<T>((
static_cast<u128>(k) * m) % lcm)) % lcm;
2928inline constexpr long double LOG_ZERO = -INFINITY;
2929inline constexpr long double LOG_ONE = 0.0;
2931inline long double log_space(
long double x) {
2932 return x == 0.0 ? LOG_ZERO : std::log(x);
2936inline long double add_log_space(
long double a,
long double b) {
2941 return a + std::log1p(std::exp(
static_cast<
double>(b - a)));
2946inline long double sub_log_space(
long double a,
long double b) {
2951 return a + std::log1p(-std::exp(
static_cast<
double>(b - a)));
2960 tgen_ensure(n > 0,
"math: number to factor must be positive");
2961 auto factors = detail::factor(n);
2962 std::sort(factors.begin(), factors.end());
2970 tgen_ensure(n > 0,
"math: number to factor must be positive");
2971 std::vector<std::pair<uint64_t,
int>> primes;
2972 for (uint64_t p : factor(n)) {
2973 if (!primes.empty()
and primes.back().first == p)
2974 ++primes.back().second;
2976 primes.emplace_back(p, 1);
2985 return static_cast<uint64_t>(detail::modular_inverse_128(a, mod));
2991 tgen_ensure(n > 0,
"math: totient(0) is undefined");
2994 for (
auto [p, e] : factor_by_prime(n))
3001inline const std::pair<std::vector<uint64_t>, std::vector<uint64_t>> &
3004 static const std::pair<std::vector<uint64_t>, std::vector<uint64_t>> value{
3006 2, 3, 7, 23, 89, 113, 523, 887, 1129, 1327, 9551, 15683, 19609,
3007 31397, 155921, 360653, 370261, 492113, 1349533, 1357201, 2010733,
3008 4652353, 17051707, 20831323, 47326693, 122164747, 189695659,
3009 191912783, 387096133, 436273009, 1294268491, 1453168141,
3010 2300942549, 3842610773, 4302407359, 10726904659, 20678048297,
3011 22367084959, 25056082087, 42652618343, 127976334671, 182226896239,
3012 241160624143, 297501075799, 303371455241, 304599508537,
3013 416608695821, 461690510011, 614487453523, 738832927927,
3014 1346294310749, 1408695493609, 1968188556461, 2614941710599,
3015 7177162611713, 13829048559701, 19581334192423, 42842283925351,
3016 90874329411493, 171231342420521, 218209405436543, 1189459969825483,
3017 1686994940955803, 1693182318746371, 43841547845541059,
3018 55350776431903243, 80873624627234849, 203986478517455989,
3019 218034721194214273, 305405826521087869, 352521223451364323,
3020 401429925999153707, 418032645936712127, 804212830686677669,
3021 1425172824437699411, 5733241593241196731, 6787988999657777797
3023 {1, 2, 4, 6, 8, 14, 18, 20, 22, 34, 36,
3024 44, 52, 72, 86, 96, 112, 114, 118, 132, 148, 154,
3025 180, 210, 220, 222, 234, 248, 250, 282, 288, 292, 320,
3026 336, 354, 382, 384, 394, 456, 464, 468, 474, 486, 490,
3027 500, 514, 516, 532, 534, 540, 582, 588, 602, 652, 674,
3028 716, 766, 778, 804, 806, 906, 916, 924, 1132, 1184, 1198,
3029 1220, 1224, 1248, 1272, 1328, 1356, 1370, 1442, 1476, 1488, 1510}};
3038 throw detail::there_is_no_upto_error(
"prime gap", right);
3040 const auto &[P, G] = prime_gaps();
3041 for (
int i =
static_cast<
int>(P.size()) - 1;; --i) {
3045 uint64_t real_right = std::min(right, P[i] + G[i] - 1);
3046 uint64_t prev = i > 0 ? G[i - 1] : 0;
3047 uint64_t curr = real_right - P[i];
3050 return {P[i] + 1, real_right};
3057 static const std::vector<uint64_t> highly_composites = {
3058 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680,
3059 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440,
3060 83160, 110880, 166320, 221760, 277200, 332640, 498960, 554400, 665280,
3061 720720, 1081080, 1441440, 2162160, 2882880, 3603600, 4324320, 6486480,
3062 7207200, 8648640, 10810800, 14414400, 17297280, 21621600, 32432400,
3063 36756720, 43243200, 61261200, 73513440, 110270160, 122522400, 147026880,
3064 183783600, 245044800, 294053760, 367567200, 551350800, 698377680, 735134400,
3065 1102701600, 1396755360, 2095133040, 2205403200, 2327925600, 2793510720,
3066 3491888400, 4655851200, 5587021440, 6983776800, 10475665200, 13967553600,
3067 20951330400, 27935107200, 41902660800, 48886437600, 64250746560,
3068 73329656400, 80313433200, 97772875200, 128501493120, 146659312800,
3069 160626866400, 240940299600, 293318625600, 321253732800, 481880599200,
3070 642507465600, 963761198400, 1124388064800, 1606268664000, 1686582097200,
3071 1927522396800, 2248776129600, 3212537328000, 3373164194400, 4497552259200,
3072 6746328388800, 8995104518400, 9316358251200, 13492656777600, 18632716502400,
3073 26985313555200, 27949074753600, 32607253879200, 46581791256000,
3074 48910880818800, 55898149507200, 65214507758400, 93163582512000,
3075 97821761637600, 130429015516800, 195643523275200, 260858031033600,
3076 288807105787200, 391287046550400, 577614211574400, 782574093100800,
3077 866421317361600, 1010824870255200, 1444035528936000, 1516237305382800,
3078 1732842634723200, 2021649740510400, 2888071057872000, 3032474610765600,
3079 4043299481020800, 6064949221531200, 8086598962041600, 10108248702552000,
3080 12129898443062400, 18194847664593600, 20216497405104000, 24259796886124800,
3081 30324746107656000, 36389695329187200, 48519593772249600, 60649492215312000,
3082 72779390658374400, 74801040398884800, 106858629141264000,
3083 112201560598327200, 149602080797769600, 224403121196654400,
3084 299204161595539200, 374005201994424000, 448806242393308800,
3085 673209363589963200, 748010403988848000, 897612484786617600,
3086 1122015605983272000, 1346418727179926400, 1795224969573235200,
3087 2244031211966544000, 2692837454359852800, 3066842656354276800,
3088 4381203794791824000, 4488062423933088000, 6133685312708553600,
3089 8976124847866176000, 9200527969062830400, 12267370625417107200ULL,
3090 15334213281771384000ULL, 18401055938125660800ULL};
3091 return highly_composites;
3096 for (
int i =
static_cast<
int>(highly_composites().size()) - 1; i >= 0; --i)
3097 if (highly_composites()[i] <= right)
3098 return highly_composites()[i];
3100 throw detail::there_is_no_upto_error(
"highly composite number", right);
3106 if (right < left
or right < 2)
3107 throw detail::there_is_no_in_range_error(
"prime", left, right);
3108 left = std::max<uint64_t>(left, 2);
3111 return next(left, right);
3112 auto [l_gap, r_gap] = prime_gap_upto(right);
3113 if (right - left + 1 <= r_gap - l_gap + 1) {
3115 std::vector<uint64_t> vals(right - left + 1);
3116 iota(vals.begin(), vals.end(), left);
3117 shuffle(vals.begin(), vals.end());
3118 for (uint64_t i : vals)
3121 throw detail::there_is_no_in_range_error(
"prime", left, right);
3126 n = next(left, right);
3134 tgen_ensure(left <= std::numeric_limits<uint64_t>::max() - 58,
3135 "math: invalid bound");
3136 for (uint64_t i = std::max<uint64_t>(2, left);; ++i)
3144 for (uint64_t i = right; i >= 2; --i)
3147 throw detail::there_is_no_upto_error(
"prime", right);
3154 for (
auto [p, e] : factor_by_prime(n))
3155 divisors *= (e + 1);
3163 int divisor_count) {
3165 "math: divisor count must be prime");
3166 int root = divisor_count - 1;
3167 uint64_t lo = detail::kth_root_floor(left, root);
3168 if (*detail::expo(lo, root, left) < left)
3170 uint64_t p =
gen_prime(lo
, detail::kth_root_floor(right, root)
);
3171 return *detail::expo(p, root, right);
3178 std::vector<uint64_t> rems,
3179 std::vector<uint64_t> mods) {
3181 throw detail::there_is_no_in_range_error(
"congruent number", left,
3184 "math: number of remainders and mods must be the same");
3185 tgen_ensure(rems.size() > 0,
"math: must have at least one congruence");
3188 for (size_t i = 0; i < rems.size(); ++i)
3190 "math: remainder must be smaller than the mod");
3193 for (
int i = 0; i <
static_cast<
int>(rems.size()); ++i) {
3194 crt = crt * detail::crt(rems[i], mods[i]);
3197 throw detail::there_is_no_in_range_error(
"congruent number", left,
3199 if (crt.m > right) {
3200 if (!(left <= crt.a
and crt.a <= right))
3201 throw detail::there_is_no_in_range_error(
"congruent number",
3204 for (
int j = 0; j <
static_cast<
int>(rems.size()); ++j)
3205 if (crt.a % mods[j] != rems[j])
3206 throw detail::there_is_no_in_range_error(
"congruent number",
3208 return static_cast<uint64_t>(crt.a);
3215 :
static_cast<uint64_t>(((left - crt.a) + crt.m - 1) / crt.m);
3216 uint64_t k_max =
static_cast<uint64_t>((right - crt.a) / crt.m);
3219 throw detail::there_is_no_in_range_error(
"congruent number", left,
3222 return static_cast<uint64_t>(crt.a + next(k_min, k_max) * crt.m);
3229 return gen_congruent(left, right, std::vector<uint64_t>({rem}),
3230 std::vector<uint64_t>({mod}));
3238 std::vector<uint64_t> mods) {
3240 "math: number of remainders and mods must be the same");
3241 tgen_ensure(rems.size() > 0,
"math: must have at least one congruence");
3244 for (size_t i = 0; i < rems.size(); ++i)
3246 "math: remainder must be smaller than the mod");
3249 for (
int i = 0; i <
static_cast<
int>(rems.size()); ++i) {
3250 crt = crt * detail::crt(rems[i], mods[i]);
3253 throw detail::there_is_no_from_error(
"congruent number", left);
3254 if (crt.m > std::numeric_limits<uint64_t>::max()) {
3256 throw detail::error(
3257 "math: congruent number does not exist or is too large");
3259 for (
int j = 0; j <
static_cast<
int>(rems.size()); ++j)
3260 if (crt.a % mods[j] != rems[j])
3261 throw detail::error(
"math: congruent number does "
3262 "not exist or is too large");
3263 return static_cast<uint64_t>(crt.a);
3269 k =
static_cast<uint64_t>(((left - crt.a) + crt.m - 1) / crt.m);
3270 detail::i128 result = crt.a + k * crt.m;
3272 if (result > std::numeric_limits<uint64_t>::max())
3273 throw detail::error(
"math: congruent number is too large");
3274 return static_cast<uint64_t>(result);
3280 return congruent_from(left, std::vector<uint64_t>{rem},
3281 std::vector<uint64_t>{mod});
3289 std::vector<uint64_t> mods) {
3291 "math: number of remainders and mods must be the same");
3292 tgen_ensure(rems.size() > 0,
"math: must have at least one congruence");
3295 for (size_t i = 0; i < rems.size(); ++i)
3297 "math: remainder must be smaller than the mod");
3300 for (
int i = 0; i <
static_cast<
int>(rems.size()); ++i) {
3302 crt = crt * detail::crt(rems[i], mods[i]);
3305 throw detail::there_is_no_upto_error(
"congruent number", right);
3306 if (crt.m > right) {
3307 if (!(crt.a <= right))
3308 throw detail::there_is_no_upto_error(
"congruent number", right);
3310 for (
int j = 0; j <
static_cast<
int>(rems.size()); ++j)
3311 if (crt.a % mods[j] != rems[j])
3312 throw detail::there_is_no_upto_error(
"congruent number",
3314 return static_cast<uint64_t>(crt.a);
3319 throw detail::there_is_no_upto_error(
"congruent number", right);
3321 uint64_t k =
static_cast<uint64_t>((right - crt.a) / crt.m);
3322 detail::i128 result = crt.a + k * crt.m;
3325 throw detail::there_is_no_upto_error(
"congruent number", right);
3326 return static_cast<uint64_t>(result);
3332 return congruent_upto(right, std::vector<uint64_t>{rem},
3333 std::vector<uint64_t>{mod});
3341 static const std::vector<uint64_t> fib = [] {
3342 std::vector<uint64_t> v = {0, 1};
3344 std::numeric_limits<uint64_t>::max() - v[v.size() - 2])
3345 v.push_back(v.back() + v[v.size() - 2]);
3357 std::optional<
int> part_right = std::nullopt) {
3358 if (!part_right.has_value())
3360 part_right = std::min(*part_right, n);
3362 "math: invalid parameters to gen_partition");
3366 (n - 1) / *part_right + 1 <= n / part_left,
3367 "math: no such partition");
3368 if (part_left == *part_right)
3369 return std::vector<
int>(n / part_left, part_left);
3370 if (n / part_left == 1)
3375 std::vector<
long double> dp(
static_cast<size_t>(n) + 1, detail::LOG_ZERO);
3376 std::vector<
long double> suffix(dp.size());
3377 dp[0] = detail::LOG_ONE;
3378 int width = *part_right - part_left + 1, block_start = 0;
3379 long double prefix = detail::LOG_ZERO;
3380 for (
int r = 0; r <= n - part_left; ++r) {
3381 if (r - block_start == width) {
3384 for (
int j = r - 1; j > block_start; --j) {
3387 suffix[j] = detail::add_log_space(suffix[j], suffix[j + 1]);
3390 prefix = detail::LOG_ZERO;
3392 prefix = detail::add_log_space(prefix, dp[r]);
3393 long double window = prefix;
3394 int l = r - width + 1;
3395 if (0 < l
and l < block_start)
3396 window = detail::add_log_space(window, suffix[l]);
3397 dp[r + part_left] = window;
3400 std::vector<
int> part;
3403 int l = std::max(0, sum - *part_right), r = sum - part_left;
3404 long double random =
3405 detail::log_space(next<
long double>(0, 1)) + dp[sum];
3406 long double cumulative = detail::LOG_ZERO;
3410 for (
int j = r; j >= l; --j) {
3411 if (dp[j] == detail::LOG_ZERO)
3414 cumulative = detail::add_log_space(cumulative, dp[j]);
3415 if (random < cumulative)
3418 detail::tgen_ensure_against_bug(nxt_sum >= 0,
3419 "math: no completion in gen_partition");
3420 part.push_back(sum - nxt_sum);
3435 std::optional<
int> part_right = std::nullopt) {
3436 if (!part_right.has_value())
3438 part_right = std::min(*part_right, n);
3440 "math: invalid parameters to gen_partition_fixed_size");
3441 tgen_ensure(
static_cast<
long long>(k) * part_left <= n
and
3442 n <=
static_cast<
long long>(k) * (*part_right),
3443 "math: no such partition");
3446 int s = n - k * part_left;
3448 std::vector<
int> part(k);
3449 if (*part_right == n) {
3451 std::vector<
int> cuts = {-1};
3454 long long total_wide =
static_cast<
long long>(s) + k - 1;
3455 if (total_wide > std::numeric_limits<
int>::max()) {
3458 auto wide_cuts = distinct_range<
long long>(0, total_wide - 1)
3461 std::sort(wide_cuts.begin(), wide_cuts.end());
3462 wide_cuts.push_back(total_wide);
3463 long long previous = -1;
3464 for (
int i = 0; i < k; ++i) {
3466 static_cast<
int>(wide_cuts[i] - previous - 1) + part_left;
3467 previous = wide_cuts[i];
3471 int total =
static_cast<
int>(total_wide), bars = k - 1;
3472 for (
int i = 0; i < total
and bars > 0; ++i)
3473 if (next<
long double>(0, 1) <
3474 static_cast<
long double>(bars) / (total - i)) {
3478 cuts.push_back(total);
3481 for (
int i = 0; i < k; ++i)
3482 part[i] = cuts[i + 1] - cuts[i] - 1;
3485 int u = *part_right - part_left;
3488 long long capacity =
static_cast<
long long>(k) * u;
3489 bool complement = s > capacity - s;
3491 s =
static_cast<
int>(capacity - s);
3493 return std::vector<
int>(k, complement ? *part_right : part_left);
3496 std::vector<std::vector<
long double>> dp(
3497 k + 1, std::vector<
long double>(s + 1, detail::LOG_ZERO));
3498 dp[0][0] = detail::LOG_ONE;
3499 std::vector<
long double> suffix(s + 1);
3501 for (
int i = 1; i <= k; ++i) {
3502 long long row_max =
static_cast<
long long>(i) * u;
3503 int middle =
static_cast<
int>(std::min<
long long>(s, row_max / 2));
3505 std::min(middle / (u + 1) * (u + 1) - 1,
3506 static_cast<
int>(std::min<
long long>(s, row_max - u)));
3509 for (
int j = suffix_max; j >= 0; --j) {
3510 suffix[j] = dp[i - 1][j];
3511 if (j < suffix_max
and j % (u + 1) != u)
3512 suffix[j] = detail::add_log_space(suffix[j], suffix[j + 1]);
3515 long double prefix = detail::LOG_ZERO;
3516 for (
int j = 0; j <= middle; ++j) {
3517 if (j % (u + 1) == 0)
3518 prefix = detail::LOG_ZERO;
3519 prefix = detail::add_log_space(prefix, dp[i - 1][j]);
3521 if (j > u
and j % (u + 1) != u)
3522 dp[i][j] = detail::add_log_space(prefix, suffix[j - u]);
3525 for (
int j = middle + 1; j <= std::min<
long long>(s, row_max); ++j)
3526 dp[i][j] = dp[i][
static_cast<
int>(row_max - j)];
3530 int left_to_distribute = s;
3531 for (
int i = k; i >= 1; --i) {
3532 long double log_total = dp[i][left_to_distribute];
3533 int lower =
static_cast<
int>(std::max<
long long>(
3534 0, left_to_distribute -
static_cast<
long long>(i - 1) * u));
3535 int upper = std::min(u, left_to_distribute);
3536 detail::tgen_ensure_against_bug(
3537 log_total != detail::LOG_ZERO,
3538 "math: total == 0 in gen_partition_fixed_size");
3544 long double random =
3545 detail::log_space(next<
long double>(0, 1)) + log_total;
3547 long double cur_prob = detail::LOG_ZERO;
3550 for (
int j = lower; j < upper; ++j) {
3551 cur_prob = detail::add_log_space(
3552 cur_prob, dp[i - 1][left_to_distribute - j]);
3553 if (random < cur_prob) {
3559 part[k - i] = complement ? u - chosen : chosen;
3560 left_to_distribute -= chosen;
3577 uint64_t n,
int k, uint64_t part_left = 0,
3578 std::optional<uint64_t> part_right = std::nullopt) {
3579 if (!part_right.has_value())
3581 part_right = std::min(*part_right, n);
3583 detail::u128 n128 = n;
3584 detail::u128 k128 = k;
3585 detail::u128 part_left128 = part_left;
3586 detail::u128 part_right128 = *part_right;
3589 "math: invalid parameters to gen_partition_fixed_size_fast");
3591 k128 * part_left128 <= n128
and
3592 k128 * part_right128 >= n128,
3593 "math: no such partition");
3595 uint64_t slack_total =
static_cast<uint64_t>(n128 - k128 * part_left128);
3596 uint64_t slack_max =
static_cast<uint64_t>(part_right128 - part_left128);
3598 std::vector<uint64_t> part(k);
3600 part[0] = slack_total;
3602 std::vector<uint64_t> cuts(k - 1);
3603 for (uint64_t &d : cuts)
3604 d = next<uint64_t>(0, slack_total);
3605 std::sort(cuts.begin(), cuts.end());
3608 for (
int i = 0; i + 1 < k; ++i) {
3609 part[i] = cuts[i] - prev;
3612 part[k - 1] = slack_total - prev;
3615 auto add_part_left = [part_left](uint64_t x) -> uint64_t {
3616 detail::u128 val = x + part_left;
3617 detail::tgen_ensure_against_bug(
3618 val <= std::numeric_limits<uint64_t>::max(),
3619 "math: part + part_left exceeds uint64_t in "
3620 "gen_partition_fixed_size_fast");
3621 return static_cast<uint64_t>(val);
3624 if (slack_max >= slack_total) {
3625 for (uint64_t &x : part)
3626 x = add_part_left(x);
3630 detail::u128 remaining = 0;
3631 for (uint64_t &x : part) {
3632 if (x > slack_max) {
3633 remaining += x - slack_max;
3636 x = add_part_left(x);
3639 if (remaining > 0) {
3640 for (uint64_t &x : part) {
3641 if (x < *part_right && remaining > 0) {
3642 detail::u128 room = *part_right - x;
3643 detail::u128 add = std::min(remaining, room);
3644 detail::u128 val = x + add;
3645 detail::tgen_ensure_against_bug(
3647 "math: part exceeds part_right after redistribution in "
3648 "gen_partition_fixed_size_fast");
3649 x =
static_cast<uint64_t>(val);
3653 detail::tgen_ensure_against_bug(
3654 remaining == 0,
"math: remaining mass after redistribution in "
3655 "gen_partition_fixed_size_fast");
3665template <
typename T>
3668 std::optional<uint64_t> max_size = std::nullopt) {
3669 size_t n = elements.size();
3670 tgen_ensure(k > 0,
"math: partition_elements: k must be positive");
3672 "math: partition_elements: min_size must be non-negative");
3674 std::vector<uint64_t> sizes;
3675 if (max_size.has_value()) {
3676 sizes = gen_partition_fixed_size_fast(n, k, min_size, max_size);
3679 gen_partition_fixed_size(
static_cast<
int>(n), k, min_size))
3680 sizes.push_back(sz);
3683 std::vector<std::vector<T>> groups;
3686 for (uint64_t sz : sizes) {
3687 groups.emplace_back(elements.begin() + pos,
3688 elements.begin() + pos + sz);
3697
3698
3699
3700
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3743 std::vector<regex_node> children_;
3744 int left_bound_, right_bound_;
3747 log_space_num_ways_;
3752 regex_node(
const std::string &pattern)
3753 : pattern_(pattern), left_bound_(-1), right_bound_(-1) {
3754 if (pattern.size() == 1) {
3755 log_space_num_ways_ = math::detail::LOG_ONE;
3758 tgen_ensure_against_bug(pattern[0] ==
'[' and pattern.back() ==
']',
3759 "str: invalid regex: expected character class");
3760 int size =
static_cast<
int>(pattern.size()) - 2;
3761 log_space_num_ways_ =
3762 static_cast<
double>(math::detail::log_space(size));
3763 distinct_ = distinct_container<
char>(pattern.substr(1, size));
3766 regex_node(
const std::string &pattern, std::vector<regex_node> &children)
3767 : pattern_(pattern), left_bound_(-1), right_bound_(-1) {
3768 if (pattern ==
"SEQ") {
3770 log_space_num_ways_ = math::detail::LOG_ONE;
3771 for (
const auto &child : children)
3772 log_space_num_ways_ += child.log_space_num_ways_;
3773 }
else if (pattern ==
"OR") {
3775 log_space_num_ways_ = math::detail::LOG_ZERO;
3776 for (
const auto &child : children)
3777 log_space_num_ways_ =
3778 static_cast<
double>(math::detail::add_log_space(
3779 log_space_num_ways_, child.log_space_num_ways_));
3781 tgen_ensure_against_bug(
"str: invalid regex: expected SEQ or OR");
3783 children_ = std::move(children);
3787 regex_node(
int left_bound,
int right_bound, regex_node &child)
3788 : pattern_(
"REP"), left_bound_(left_bound), right_bound_(right_bound) {
3789 log_space_num_ways_ = math::detail::LOG_ZERO;
3790 for (
int i = left_bound; i <= right_bound; ++i)
3791 log_space_num_ways_ =
3792 static_cast<
double>(math::detail::add_log_space(
3793 log_space_num_ways_, i * child.log_space_num_ways_));
3795 children_.push_back(std::move(child));
3801 std::vector<regex_node> cur;
3802 std::vector<regex_node> branches;
3806inline regex_node make_regex_seq(regex_state &st) {
3807 return regex_node(
"SEQ", st.cur);
3811inline regex_node finish_regex_state(regex_state &st) {
3813 if (st.branches.empty())
3814 return make_regex_seq(st);
3817 st.branches.push_back(make_regex_seq(st));
3818 return regex_node(
"OR", st.branches);
3823inline regex_node parse_regex(std::string regex) {
3824 std::string new_regex;
3825 for (
char c : regex)
3828 swap(regex, new_regex);
3830 std::vector<regex_state> stack;
3832 for (size_t i = 0; i < regex.size(); ++i) {
3837 stack.push_back(std::move(cur));
3838 cur = regex_state();
3839 }
else if (c ==
')') {
3841 regex_node node = finish_regex_state(cur);
3843 tgen_ensure(!stack.empty(),
"str: invalid regex: unmatched `)`");
3844 cur = std::move(stack.back());
3847 cur.cur.push_back(std::move(node));
3848 }
else if (c ==
'|') {
3850 regex_node node = make_regex_seq(cur);
3851 cur.branches.push_back(std::move(node));
3852 }
else if (c ==
'[') {
3856 for (++i; i < regex.size()
and regex[i] !=
']'; ++i) {
3857 if (i + 2 < regex.size()
and regex[i + 1] ==
'-') {
3858 char a = regex[i], b = regex[i + 2];
3862 for (
int x = a; x <= b; ++x)
3863 chars +=
static_cast<
char>(x);
3870 "str: invalid regex: unmatched `[`");
3871 cur.cur.emplace_back(
"[" + chars +
"]");
3872 }
else if (c ==
'{') {
3877 while (i < regex.size()
and
3878 isdigit(
static_cast<
unsigned char>(regex[i]))) {
3882 "str: invalid regex: number too large inside `{}`");
3883 l = 10 * l + (regex[i] -
'0');
3887 if (i < regex.size()
and regex[i] ==
',') {
3889 while (i < regex.size()
and
3890 isdigit(
static_cast<
unsigned char>(regex[i]))) {
3894 r <=
static_cast<
int>(1e8),
3895 "str: invalid regex: number too large inside `{}`");
3896 r = 10 * r + (regex[i] -
'0');
3903 "str: invalid regex: unmatched `{`");
3905 "str: invalid regex: missing number inside `{}`");
3907 "str: invalid regex: invalid range inside `{}`");
3911 "str: invalid regex: expected expression before `{}`");
3913 regex_node rep(l, r, cur.cur.back());
3915 cur.cur.push_back(std::move(rep));
3918 cur.cur.emplace_back(std::string(1, c));
3922 tgen_ensure(stack.empty(),
"str: invalid regex: unmatched `(`");
3923 return finish_regex_state(cur);
3927inline void gen_regex(
const regex_node &node, std::string &str) {
3929 if (node.pattern_[0] ==
'[') {
3930 str += node.pattern_[1 + next<
int>(
3931 0,
static_cast<
int>(node.pattern_.size()) -
3937 if (node.left_bound_ != -1) {
3942 static_cast<
double>(math::detail::log_space(next<
double>(0, 1))) +
3943 node.log_space_num_ways_;
3944 double cur_prob = math::detail::LOG_ZERO;
3945 double child_num_ways = node.children_[0].log_space_num_ways_;
3947 for (
int i = node.left_bound_; i <= node.right_bound_; ++i) {
3948 cur_prob =
static_cast<
double>(
3949 math::detail::add_log_space(cur_prob, i * child_num_ways));
3950 if (log_rand <= cur_prob) {
3951 for (
int j = 0; j < i; ++j)
3952 gen_regex(node.children_[0], str);
3957 tgen_ensure_against_bug(
false,
3958 "str: log_rand > cur_prob in REP gen_regex");
3962 if (node.pattern_ ==
"SEQ") {
3963 for (
const regex_node &child : node.children_)
3964 gen_regex(child, str);
3969 if (!node.children_.empty()
and node.pattern_ ==
"OR") {
3974 static_cast<
double>(math::detail::log_space(next<
double>(0, 1))) +
3975 node.log_space_num_ways_;
3976 double cur_prob = math::detail::LOG_ZERO;
3978 for (
const regex_node &child : node.children_) {
3979 cur_prob =
static_cast<
double>(math::detail::add_log_space(
3980 cur_prob, child.log_space_num_ways_));
3981 if (log_rand <= cur_prob) {
3982 gen_regex(child, str);
3987 tgen_ensure_against_bug(
false,
3988 "str: log_rand > cur_prob in OR gen_regex");
3992 detail::tgen_ensure_against_bug(
3993 node.pattern_.size() == 1,
3994 "str: invalid regex: expected single character, but got `" +
3995 node.pattern_ +
"`");
3996 str += node.pattern_[0];
4000template <
typename... Args>
4001std::string regex_format(
const std::string &s, Args &&...args) {
4002 if constexpr (
sizeof...(Args) == 0) {
4005 int size = std::snprintf(
nullptr, 0, s.c_str(), args...) + 1;
4006 std::string buf(size,
'\0');
4007 std::snprintf(buf.data(), size, s.c_str(), args...);
4016
4017
4020 std::optional<
list<
char>> list_;
4021 std::optional<detail::regex_node>
4026 str(
int size,
char value_left =
'a',
char value_right =
'z') {
4027 tgen_ensure(size > 0,
"str: size must be positive");
4028 list_ = list<
char>(size, value_left, value_right);
4033 str(
int size, std::set<
char> chars) {
4034 tgen_ensure(size > 0,
"str: size must be positive");
4035 list_ = list<
char>(size, chars);
4039 template <
typename... Args>
str(
const std::string ®ex, Args &&...args) {
4040 tgen_ensure(regex.size() > 0,
"str: regex must be non-empty");
4042 root_ = detail::parse_regex(
4043 detail::regex_format(regex, std::forward<Args>(args)...));
4048 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4049 list_->fix(idx, character);
4055 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4056 list_->equal(indices);
4062 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4063 list_->equal(idx_1, idx_2);
4069 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4070 list_->equal_range(left, right);
4076 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4083 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4084 tgen_ensure(0 <= left
and left <= right
and right < list_->size_,
4085 "str: range indices must be valid");
4086 for (
int i = left; i < right - (i - left); ++i)
4093 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4094 return palindrome(0, list_->size_ - 1);
4100 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4101 list_->different(indices);
4107 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4108 list_->different(idx_1, idx_2);
4114 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4115 list_->different_range(left, right);
4121 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4122 list_->all_different();
4128 tgen_ensure(!root_,
"str: cannot add restriction for regex");
4129 list_->adjacent_different();
4135 using tgen_is_sequential_tag = detail::is_sequential_tag;
4137 using value_type =
char;
4138 using std_type = std::string;
4141 value(
const std::string &str) : str_(str) {}
4144 int size()
const {
return static_cast<
int>(str_.size()); }
4149 "str: value: index out of bounds");
4152 const char &operator[](
int idx)
const {
4154 "str: value: index out of bounds");
4161 std::sort(str_.begin(), str_.end());
4168 std::reverse(str_.begin(), str_.end());
4175 for (
char &c : str_)
4176 c =
static_cast<
char>(
4177 std::tolower(
static_cast<
unsigned char>(c)));
4184 for (
char &c : str_)
4185 c =
static_cast<
char>(
4186 std::toupper(
static_cast<
unsigned char>(c)));
4193 return value(str_ + rhs.str_
);
4199 tgen::shuffle(str_.begin(), str_.end());
4209 template <
typename Dist>
4212 "value and distribution must have the same size");
4213 return str_[next_by_distribution(distribution)];
4215 template <
typename Dist>
4216 char pick_by_distribution(
4217 const std::initializer_list<Dist> &distribution)
const {
4218 return pick_by_distribution(std::vector<Dist>(distribution));
4225 "number of elements to choose must be valid");
4226 std::string new_str;
4228 for (
int i = 0; need > 0; ++i) {
4230 if (next(1, left) <= need) {
4231 new_str.push_back(str_[i]);
4239 friend std::ostream &operator<<(std::ostream &out,
const value &val) {
4240 return out << val.str_;
4244 std::string
to_std()
const {
return std_type(str_); }
4253 std::string ret_str;
4254 gen_regex(*root_, ret_str);
4258 std::vector<
char> vec = list_->gen().to_std();
4259 return value(std::string(vec.begin(), vec.end()));
4265
4266
4267
4268
4274template <
typename T> std::pair<T, T> gen_eq(T L1, T R1, T L2, T R2) {
4275 T L = std::max(L1, L2);
4276 T R = std::min(R1, R2);
4278 tgen_ensure(L <= R,
"pair: no valid values to generate");
4279 T x = next<T>(L, R);
4284template <
typename T>
4285std::pair<u128, u128> get_n_and_m(T L1, T R1, T L2, T R2) {
4286 u128 n =
static_cast<i128>(R1) - L1 + 1;
4287 u128 m =
static_cast<i128>(R2) - L2 + 1;
4293static u128 pos_arith_sum(u128 first, u128 last, u128 num_terms) {
4294 u128 x = first + last, y = num_terms;
4307template <
typename T> std::pair<T, T> gen_neq(T L1, T R1, T L2, T R2) {
4308 auto [n, m] = get_n_and_m(L1, R1, L2, R2);
4310 T L_intersect = std::max(L1, L2);
4311 T R_intersect = std::min(R1, R2);
4312 u128 inter =
static_cast<i128>(R_intersect) - L_intersect + 1;
4314 u128 total = n * m - inter;
4315 tgen_ensure(total > 0,
"pair: no valid values to generate");
4320 a = next<T>(L1, R1);
4321 b = next<T>(L2, R2);
4332template <
typename T>
4333std::pair<u128, u128> count_lt_regions(T L1, T R1, T L2, T R2) {
4334 auto [n, m] = get_n_and_m(L1, R1, L2, R2);
4337 i128 L_second = std::max<i128>(L2,
static_cast<i128>(L1) + 1);
4341 i128 split = std::min<i128>(R_second, R1);
4344 u128 len1 = std::max<i128>(0, split - L_second + 1);
4346 u128 count_region1 = 0;
4349 i128 first = L_second - L1;
4350 i128 last = split - L1;
4353 count_region1 = pos_arith_sum(first, last, len1);
4358 i128 L_second_region2 = std::max(L_second,
static_cast<i128>(R1) + 1);
4360 u128 len2 = std::max<i128>(0, R_second - L_second_region2 + 1);
4361 u128 count_region2 = len2 * n;
4363 return {count_region1, count_region2};
4368template <
typename T> std::pair<T, T> gen_lt(T L1, T R1, T L2, T R2) {
4369 auto [n, m] = get_n_and_m(L1, R1, L2, R2);
4373 i128 L_second = std::max<i128>(L2,
static_cast<i128>(L1) + 1);
4379 i128 split = std::min<i128>(R_second, R1);
4381 auto [count_region1, count_region2] = count_lt_regions(L1, R1, L2, R2);
4382 u128 total = count_region1 + count_region2;
4383 tgen_ensure(total > 0,
"pair: no valid values to generate");
4385 u128 k = detail::next128(total);
4386 if (k < count_region1) {
4390 u128 len1 = std::max<i128>(0, split - L_second + 1);
4397 i128 base = L_second - L1;
4398 i128 lo = 0, hi =
static_cast<i128>(len1) - 1;
4401 i128 mid = lo + (hi - lo) / 2;
4403 if (pos_arith_sum(base, base + mid, mid + 1) <= k)
4412 k -= pos_arith_sum(base, base + d - 1, d);
4415 return {
static_cast<T>(i128(L1) + i128(k)),
4416 static_cast<T>(L_second + d)};
4422 i128 L_second_region2 = std::max(L_second,
static_cast<i128>(R1) + 1);
4425 return {
static_cast<T>(i128(L1) + i128(k % n)),
4426 static_cast<T>(L_second_region2 + i128(k / n))};
4432template <
typename T> std::pair<T, T> gen_gt(T L1, T R1, T L2, T R2) {
4433 auto [first, second] = gen_lt(L2, R2, L1, R1);
4434 return {second, first};
4439template <
typename T> std::pair<T, T> gen_leq(T L1, T R1, T L2, T R2) {
4441 i128 L_intersect = std::max(L1, L2);
4442 i128 R_intersect = std::min(R1, R2);
4443 u128 eq_count = std::max<i128>(0, R_intersect - L_intersect + 1);
4446 auto [lt_region1, lt_region2] = count_lt_regions(L1, R1, L2, R2);
4447 u128 lt_count = lt_region1 + lt_region2;
4449 u128 total = eq_count + lt_count;
4450 tgen_ensure(total > 0,
"pair: no valid values to generate");
4452 if (detail::next128(total) < eq_count)
4453 return gen_eq(L1, R1, L2, R2);
4454 return gen_lt(L1, R1, L2, R2);
4459template <
typename T> std::pair<T, T> gen_geq(T L1, T R1, T L2, T R2) {
4460 auto [first, second] = gen_leq(L2, R2, L1, R1);
4461 return {second, first};
4467
4468
4469
4470
4473 std::pair<T, T> first_, second_;
4475 enum class restriction_type { eq, neq, lt, gt, leq, geq, unspecified };
4476 restriction_type type_ = restriction_type::unspecified;
4480 pair(T first_left, T first_right, T second_left, T second_right)
4481 : first_(first_left, first_right), second_(second_left, second_right) {
4483 "pair: first range must be valid");
4485 "pair: second range must be valid");
4490 :
pair(both_left, both_right, both_left, both_right) {}
4494 type_ = restriction_type::eq;
4500 type_ = restriction_type::neq;
4506 type_ = restriction_type::lt;
4512 type_ = restriction_type::gt;
4518 type_ = restriction_type::leq;
4524 type_ = restriction_type::geq;
4530 using value_type = T;
4531 using std_type = std::pair<T, T>;
4533 std::pair<T, T> pair_;
4536 value(
const std::pair<T, T> &pair) : pair_(pair), sep_(
' ') {}
4538 : pair_(first, second), sep_(
' ') {}
4550 friend std::ostream &operator<<(std::ostream &out,
const value &val) {
4551 return out << val.pair_.first << val.sep_ << val.pair_.second;
4556 if constexpr (!detail::is_generator_value<T>::value) {
4559 std::pair<
typename T::std_type,
typename T::std_type> pair(
4560 pair_.first.to_std(), pair_.second.to_std());
4569 T L1 = first_.first, R1 = first_.second;
4570 T L2 = second_.first, R2 = second_.second;
4573 case restriction_type::unspecified:
4574 return {next<T>(L1, R1), next<T>(L2, R2)};
4575 case restriction_type::eq:
4576 return detail::gen_eq<T>(L1, R1, L2, R2);
4577 case restriction_type::neq:
4578 return detail::gen_neq<T>(L1, R1, L2, R2);
4579 case restriction_type::lt:
4580 return detail::gen_lt<T>(L1, R1, L2, R2);
4581 case restriction_type::gt:
4582 return detail::gen_gt<T>(L1, R1, L2, R2);
4583 case restriction_type::leq:
4584 return detail::gen_leq<T>(L1, R1, L2, R2);
4585 case restriction_type::geq:
4586 return detail::gen_geq<T>(L1, R1, L2, R2);
4588 throw detail::error(
"pair: unknown restriction type");
4593
4594
4595
4596
4602inline std::vector<std::pair<
int,
int>> edges_from_prufer(std::vector<
int> p) {
4603 int n =
static_cast<
int>(p.size()) + 2;
4606 std::vector<
int> d(n, 1);
4615 idx = u =
static_cast<
int>(find(d.begin(), d.end(), 1) - d.begin());
4618 std::vector<std::pair<
int,
int>> edges;
4620 edges.emplace_back(u, v);
4621 if (--d[v] == 1
and v < idx)
4624 idx = u =
static_cast<
int>(find(d.begin() + idx + 1, d.end(), 1) -
4632 std::vector<
int> parent_;
4633 std::vector<
unsigned char> rank_;
4638 dsu(
int n) : parent_(n), rank_(n, 0) {
4639 for (
int i = 0; i < n; ++i)
4645 void add_elements(
int k) {
4646 for (
int i = 0; i < k; ++i) {
4647 int new_id =
static_cast<
int>(parent_.size());
4648 parent_.push_back(new_id);
4656 return parent_[i] == i ? i : parent_[i] = find(parent_[i]);
4662 bool unite(
int a,
int b) {
4667 if (rank_[a] > rank_[b])
4670 if (rank_[a] == rank_[b])
4679template <
typename VWeight,
typename EWeight>
struct wgraph;
4682
4683
4684
4685
4686
4687
4688
4689
4691template <
typename VWeight,
typename EWeight>
4694 std::set<std::pair<
int,
int>> edges_;
4699 tgen_ensure(n > 0,
"wtree: number of vertices must be positive");
4705 tgen_ensure(0 <= std::min(u, v)
and std::max(u, v) < n_,
4706 "wtree: vertices must be indexed in [0, n)");
4707 tgen_ensure(u != v,
"wtree: cannot add self loop to tree");
4711 edges_.emplace(u, v);
4723 std::vector<std::set<
int>> adj_;
4724 std::vector<std::pair<
int,
int>> edges_;
4725 bool print_1_based_;
4727 std::optional<
int> print_parents_;
4729 std::optional<std::vector<VWeight>> vertex_weights_;
4730 std::optional<std::vector<EWeight>>
4736 value(
const std::vector<std::set<
int>> &adj)
4737 : n_(
static_cast<
int>(adj.size())),
adj_(
adj),
4738 print_1_based_(
false), print_n_(
false),
dsu_(
n_) {
4739 for (
int u = 0; u < n_; ++u)
4740 for (
auto v : adj[u]) {
4743 "wtree: value: vertices must be indexed in [0, n)");
4746 edges_.emplace_back(u, v);
4749 "wtree: value: initial graph must form a tree");
4756 value(
int n,
const std::vector<std::pair<
int,
int>> &edges)
4757 : n_(n),
adj_(
n), print_1_based_(
false), print_n_(
false),
dsu_(
n) {
4758 edges_.reserve(edges.size());
4759 for (
auto [u, v] : edges) {
4760 tgen_ensure(0 <= std::min(u, v)
and std::max(u, v) < n,
4761 "wtree: value: vertices must be indexed in [0, n)");
4763 "wtree: value: initial graph must form a tree");
4766 edges_.emplace_back(u, v);
4771 value(
int n,
const std::set<std::pair<
int,
int>> &edges)
4774 value(
int n,
const std::initializer_list<std::pair<
int,
int>> &edges)
4775 : value(n, std::vector<std::pair<
int,
int>>(edges)) {}
4780 value(
const typename wgraph<VWeight, EWeight>::value &g);
4784 template <
typename NewVWeight,
typename NewEWeight>
4785 typename wtree<NewVWeight, NewEWeight>::value
4786 convert_weight_types()
const {
4788 !edge_weights_.has_value(),
4789 "wtree: value: cannot convert weight type after "
4790 "assigning weights");
4792 return copy_without_weights<NewVWeight, NewEWeight>();
4796 int n()
const {
return n_; }
4806 return vertex_weights_;
4811 return edge_weights_;
4816 template <
typename NewVWeight = VWeight>
4818 const std::vector<NewVWeight> &vertex_weights)
const {
4820 "wtree: value: must give `n` vertex weights");
4822 auto new_tree = copy_without_weights<NewVWeight, EWeight>();
4823 new_tree.edge_weights_ = edge_weights_;
4824 new_tree.vertex_weights_ = vertex_weights;
4830 template <
typename NewEWeight = EWeight>
4834 edge_weights.size() == edges().size(),
4835 "wtree: value: must give `edges().size()` edge weights");
4837 auto new_tree = copy_without_weights<VWeight, NewEWeight>();
4838 new_tree.vertex_weights_ = vertex_weights_;
4839 new_tree.edge_weights_ = edge_weights;
4847 "wtree: value: edge_weighted requires a tree with no "
4850 "wtree: value: tree is already edge-weighted");
4852 edge_weights_ = std::vector<EWeight>();
4860 print_1_based_ =
true;
4877 "wtree: value: root must be -1, `n`, or in [0, n)");
4878 print_parents_ = root;
4891 std::vector<
int> new_label(
n());
4892 std::vector<
int> shuffled;
4893 for (
int i = 0; i <
n(); ++i) {
4894 if (indices.count(i))
4897 shuffled.push_back(i);
4899 std::vector<
int> targets = shuffled;
4900 tgen::shuffle(targets.begin(), targets.end());
4901 for (size_t k = 0; k < shuffled.size(); ++k)
4902 new_label[shuffled[k]] = targets[k];
4905 std::vector<std::set<
int>> new_adj(
n());
4906 for (
int u = 0; u < n(); ++u)
4907 for (
int v : adj_[u])
4908 new_adj[new_label[u]].insert(new_label[v]);
4909 adj_ = std::move(new_adj);
4912 for (
auto &[u, v] : edges_) {
4920 if (vertex_weights_.has_value()) {
4921 std::vector<VWeight> new_vw(
n());
4922 for (
int i = 0; i < n(); ++i)
4923 new_vw[new_label[i]] = (*vertex_weights_)[i];
4924 vertex_weights_ = std::move(new_vw);
4928 dsu_ = detail::dsu(n());
4929 for (
auto [u, v] : edges_)
4934 std::vector<
int> perm(edges_.size());
4935 std::iota(perm.begin(), perm.end(), 0);
4936 tgen::shuffle(perm.begin(), perm.end());
4938 std::vector<std::pair<
int,
int>> new_edges;
4939 std::optional<std::vector<EWeight>> new_ew;
4940 if (edge_weights_.has_value())
4941 new_ew = std::vector<EWeight>();
4942 for (
int i : perm) {
4943 new_edges.push_back(edges_[i]);
4944 if (new_ew.has_value())
4945 new_ew->push_back((*edge_weights_)[i]);
4948 if (new_ew.has_value())
4949 edge_weights_ = new_ew;
4960 value &add_edge(
int u,
int v, std::optional<EWeight> w = std::nullopt) {
4962 "wtree: value: vertex ids must be valid");
4967 if (adj_[u].count(v))
4972 if (w.has_value()) {
4974 "wtree: value: cannot add weighted edge to "
4975 "edge-unweighted tree");
4978 "wtree: value: cannot add unweighted edge to "
4979 "edge-weighted tree");
4982 "wtree: value: added edge must not create a cycle");
4985 edges_.emplace_back(u, v);
4987 edge_weights_->push_back(*w);
4997 std::optional<EWeight> new_w = std::nullopt) {
5006 "wtree: value: vertex ids must be valid");
5010 add_vertices(rhs.n(), rhs.vertex_weights());
5011 for (
int i = 0; i <
static_cast<
int>(rhs.edges().size()); ++i) {
5012 auto [u, v] = rhs.edges()[i];
5013 add_edge(shift + u, shift + v,
5014 rhs.edge_weights().has_value()
5015 ? std::optional<EWeight>((*rhs.edge_weights())[i])
5020 add_edge(new_u, shift + new_v, new_w);
5030 std::set<std::pair<
int,
int>> index_pairs) {
5035 return glue(copy, std::move(index_pairs));
5039 std::set<
int> idx_left, idx_right;
5040 std::vector<
int> right_id_to_left(rhs
.n(), -1);
5041 for (
auto [l, r] : index_pairs) {
5043 0 <= l
and l < n()
and 0 <= r
and r < rhs.n(),
5044 "wtree: value: vertex indices to glue must be valid");
5045 tgen_ensure(idx_left.count(l) == 0
and idx_right.count(r) == 0,
5046 "wtree: value: must not have repeated indices "
5047 "on the same side to glue");
5050 idx_right.insert(r);
5051 right_id_to_left[r] = l;
5055 std::vector<
int> new_right_id(rhs
.n(), -1);
5056 int intersection_lt = 0;
5057 std::optional<std::vector<VWeight>> rhs_vertex_weights;
5059 if (rhs.vertex_weights().has_value())
5060 rhs_vertex_weights = std::vector<VWeight>();
5061 for (
int i = 0; i < rhs
.n(); ++i) {
5062 if (right_id_to_left[i] != -1) {
5065 new_right_id[i] = right_id_to_left[i];
5068 new_right_id[i] =
n() + i - intersection_lt;
5069 if (rhs.vertex_weights().has_value()) {
5070 rhs_vertex_weights->push_back(
5071 (*rhs.vertex_weights())[i]);
5077 add_vertices(rhs.n() - intersection_lt, rhs_vertex_weights);
5078 for (
int i = 0; i <
static_cast<
int>(rhs.edges().size()); ++i) {
5079 auto [u, v] = rhs.edges()[i];
5080 add_edge(new_right_id[u], new_right_id[v],
5081 rhs.edge_weights().has_value()
5082 ? std::optional<EWeight>((*rhs.edge_weights())[i])
5089 std::initializer_list<std::pair<
int,
int>> il) {
5090 return glue(rhs, std::set<std::pair<
int,
int>>(il));
5098 std::set<std::pair<
int,
int>> index_pairs;
5099 for (
auto i : indices)
5100 index_pairs.emplace(i, i);
5101 return glue(rhs, index_pairs);
5103 value &glue(
const value &rhs,
const std::initializer_list<
int> &il) {
5104 return glue(rhs, std::set<
int>(il));
5109 friend std::ostream &operator<<(std::ostream &out,
const value &val) {
5111 out << val.n() <<
'\n';
5114 if (val.vertex_weights()) {
5115 for (
int i = 0; i < val.n(); ++i) {
5118 out << (*val.vertex_weights())[i];
5123 tgen_ensure(
static_cast<
int>(val.edges().size()) == val.n() - 1,
5124 "wtree: value: invalid tree to print (number of edges "
5125 "must be `n` - 1)");
5128 if (val.print_parents_.has_value()) {
5130 "wtree: value: cannot print parent style if edges "
5133 int root = *val.print_parents_;
5134 bool skip_parent_0 = root == -1;
5137 if (root == val.n())
5138 root = next(0, val.n() - 1);
5140 std::vector<
int> parent(val.n(), -1);
5143 std::vector<
int> vis(val.n(),
false);
5150 for (
int v : val.adj()[u])
5158 if (skip_parent_0) {
5159 for (
int i = 1; i < val.n(); ++i) {
5162 "wtree: value: parent of i must be less than i for "
5163 "printing in parent style if root is -1");
5167 out << parent[i] + val.print_1_based_;
5170 for (
int i = 0; i < val.n(); ++i) {
5173 out << (parent[i] == -1 ? -1 : parent[i]) +
5183 for (
int i = 0; i <
static_cast<
int>(val.edges().size()); ++i) {
5184 auto [u, v] = val.edges()[i];
5185 out << (u + val.print_1_based_) <<
" "
5186 << (v + val.print_1_based_);
5189 if (val.edge_weights().has_value())
5190 out <<
" " << (*val.edge_weights())[i];
5201 return std_type(n_, adj_);
5207 std::vector<std::set<
int>> adj(n_ + 1);
5208 for (
int u = 0; u < n_; ++u)
5209 for (
int v : adj_[u])
5210 adj[u + 1].insert(v + 1);
5211 return std_type(n_, adj);
5218 template <
typename NewVWeight,
typename NewEWeight>
5219 typename wtree<NewVWeight, NewEWeight>::value
5220 copy_without_weights()
const {
5221 typename wtree<NewVWeight, NewEWeight>::value new_tree(adj_);
5222 new_tree.edges_ = edges_;
5223 new_tree.print_1_based_ = print_1_based_;
5224 new_tree.print_n_ = print_n_;
5225 new_tree.print_parents_ = print_parents_;
5232 value &add_vertices(
int k, std::optional<std::vector<VWeight>>
5233 new_vertex_weights = std::nullopt) {
5237 "wtree: value: number of added vertices must be nonnegative");
5238 tgen_ensure(k <= std::numeric_limits<
int>::max() -
5239 static_cast<
long long>(n_),
5240 "wtree: value: too many vertices");
5241 if (new_vertex_weights.has_value()) {
5243 "wtree: value: cannot add weighted vertices to "
5244 "vertex-unweighted tree");
5246 static_cast<
int>(new_vertex_weights->size()) == k,
5247 "wtree: value: number of vertex weights must be equal "
5248 "to number of added vertices");
5251 "wtree: value: cannot add unweighted vertices to "
5252 "vertex-weighted tree");
5256 if (new_vertex_weights.has_value())
5257 vertex_weights_->insert(vertex_weights_->end(),
5258 new_vertex_weights->begin(),
5259 new_vertex_weights->end());
5261 dsu_.add_elements(k);
5271 std::vector<std::vector<
int>> adj(n_);
5272 for (
auto [u, v] : edges_) {
5273 adj[u].push_back(v);
5274 adj[v].push_back(u);
5277 std::vector<
int> comp_size;
5278 std::vector<std::vector<
int>> component_ids;
5279 std::vector<
bool> vis(n_,
false);
5282 for (
int i = 0; i < n_; ++i) {
5288 comp_size.push_back(0);
5289 component_ids.emplace_back();
5294 component_ids.back().push_back(u);
5295 for (
int v : adj[u]) {
5306 std::vector<std::pair<
int,
int>> new_edges(edges_.begin(),
5308 if (comp_size.size() > 1) {
5309 std::vector<
int> prufer_values = many_by_distribution(
5310 static_cast<
int>(comp_size.size()) - 2, comp_size);
5311 for (
auto [u, v] : detail::edges_from_prufer(prufer_values))
5312 new_edges.emplace_back(pick(component_ids[u]),
5313 pick(component_ids[v]));
5316 return value(n_, new_edges);
5327 std::vector<std::pair<
int,
int>> edges;
5328 for (
int i = 1; i < n; ++i)
5329 edges.emplace_back(i, wnext<
int>(i, elongation));
5330 return value(n, edges);
5337 tgen_ensure(n > 0,
"wtree: gen_kruskal: n must be positive");
5339 return value(1, {});
5341 detail::dsu components(n);
5342 std::vector<std::pair<
int,
int>> edges;
5343 edges.reserve(n - 1);
5344 while (edges.size() < size_t(n - 1)) {
5345 int u = next(0, n - 1);
5346 int v = next(0, n - 1);
5349 if (components.unite(u, v))
5350 edges.emplace_back(u, v);
5352 return value(n, edges);
5357
5358
5370
5371
5372
5373
5379inline uint64_t undirected_edge_key(
int u,
int v) {
5382 return (
static_cast<uint64_t>(u) << 32) |
5383 static_cast<uint64_t>(
static_cast<uint32_t>(v));
5388inline uint64_t directed_edge_key(
int u,
int v) {
5389 return (
static_cast<uint64_t>(u) << 32) |
5390 static_cast<uint64_t>(
static_cast<uint32_t>(v));
5395inline long long max_graph_edges(
int n,
bool directed,
bool self_loops) {
5399 return self_loops ?
static_cast<
long long>(n) * n
5400 :
static_cast<
long long>(n) * (n - 1);
5403 ?
static_cast<
long long>(n) * (
static_cast<
long long>(n) + 1) / 2
5404 :
static_cast<
long long>(n) * (n - 1) / 2;
5409inline std::pair<
int,
int> get_random_graph_edge(
int n,
bool directed,
5413 return {next<
int>(0, n - 1), next<
int>(0, n - 1)};
5414 int u = next<
int>(0, n - 1);
5415 int v = next<
int>(0, n - 1);
5417 v = next<
int>(0, n - 1);
5421 int u = next<
int>(0, n - 1);
5422 int v = next<
int>(0, n - 1);
5427 int u = next<
int>(0, n - 1);
5428 int v = next<
int>(0, n - 1);
5430 v = next<
int>(0, n - 1);
5439inline std::pair<
int,
int> decode_undirected_simple_edge(
int n,
long long idx) {
5440 auto base = [&](
int u) ->
long long {
5441 return static_cast<
long long>(u) * (n - 1) -
5442 static_cast<
long long>(u) * (u - 1) / 2;
5444 int lo = 0, hi = n - 2;
5447 int mid = lo + (hi - lo + 1) / 2;
5448 if (base(mid) <= idx)
5453 return {lo, lo + 1 +
int(idx - base(lo))};
5459inline std::pair<
int,
int> decode_undirected_loops_edge(
int n,
long long idx) {
5460 auto base = [&](
int u) ->
long long {
5461 return static_cast<
long long>(u) * n -
5462 static_cast<
long long>(u) * (u - 1) / 2;
5464 int lo = 0, hi = n - 1;
5467 int mid = lo + (hi - lo + 1) / 2;
5468 if (base(mid) <= idx)
5473 return {lo, lo +
int(idx - base(lo))};
5478inline std::pair<
int,
int> decode_directed_simple_edge(
int n,
long long idx) {
5479 int u =
static_cast<
int>(idx / (n - 1));
5480 int rem =
static_cast<
int>(idx % (n - 1));
5481 return {u, rem + (rem >= u)};
5486inline std::pair<
int,
int>
5487decode_graph_edge_index(
int n,
long long idx,
bool directed,
bool self_loops) {
5490 return {
int(idx / n),
int(idx % n)};
5491 return decode_directed_simple_edge(n, idx);
5494 return decode_undirected_loops_edge(n, idx);
5495 return decode_undirected_simple_edge(n, idx);
5501
5502
5503
5504
5505
5506
5507
5508
5510template <
typename VWeight,
typename EWeight>
5513 std::set<std::pair<
int,
int>> edges_;
5515 bool has_self_loops_;
5521 wgraph(
int n,
int m,
bool is_directed =
false,
bool has_self_loops =
false)
5522 : n_(n), m_(m), is_directed_(is_directed),
5523 has_self_loops_(has_self_loops) {
5524 tgen_ensure(n > 0,
"wgraph: number of vertices must be positive");
5530 tgen_ensure(0 <= std::min(u, v)
and std::max(u, v) < n_,
5531 "wgraph: vertices must be indexed in [0, n)");
5533 "wgraph: self loops are not allowed");
5535 if (!is_directed_
and u > v)
5537 auto [it, inserted] = edges_.emplace(u, v);
5538 if (
static_cast<
int>(edges_.size()) > m_) {
5542 throw detail::error(
"wgraph: too many edges were added");
5557 mutable std::vector<std::set<
int>> adj_;
5558 std::vector<std::pair<
int,
int>> edges_;
5560 bool print_1_based_;
5562 mutable bool adj_built_{
5565 std::optional<std::vector<VWeight>> vertex_weights_;
5566 std::optional<std::vector<EWeight>>
5572 value(
const std::vector<std::set<
int>> &adj,
bool is_directed =
false)
5573 : n_(
static_cast<
int>(adj.size())),
adj_(
adj),
5574 is_directed_(is_directed), print_1_based_(
false),
5575 print_nm_(
false), adj_built_(
true) {
5576 for (
int u = 0; u < n_; ++u)
5577 for (
auto v : adj[u]) {
5580 "wgraph: value: vertices must be indexed in [0, n)");
5584 if (is_directed_
or u <= v)
5585 edges_.emplace_back(u, v);
5593 value(
int n,
const std::vector<std::pair<
int,
int>> &edges = {},
5594 bool is_directed =
false)
5595 : n_(n),
edges_(), is_directed_(is_directed), print_1_based_(
false),
5596 print_nm_(
false), adj_built_(
false) {
5597 edges_.reserve(edges.size());
5598 std::unordered_set<uint64_t> seen;
5599 seen.reserve(edges.size() * 2 + 1);
5600 for (
auto [u, v] : edges) {
5602 0 <= std::min(u, v)
and std::max(u, v) < n,
5603 "wgraph: value: vertices must be indexed in [0, n)");
5604 if (!is_directed_
and u > v)
5606 uint64_t key = is_directed_ ? detail::directed_edge_key(u, v)
5607 : detail::undirected_edge_key(u, v);
5608 if (seen.insert(key).second)
5609 edges_.emplace_back(u, v);
5612 value(
int n,
const std::set<std::pair<
int,
int>> &edges,
5613 bool is_directed =
false)
5618 value(
int n,
const std::initializer_list<std::pair<
int,
int>> &edges,
5619 bool is_directed =
false)
5620 : value(n, std::vector<std::pair<
int,
int>>(edges), is_directed) {}
5625 :
value(t.n(), t.edges(),
false) {
5626 if (t.vertex_weights().has_value()) {
5627 vertex_weights_ = *t.vertex_weights();
5629 if (t.edge_weights().has_value()) {
5630 edge_weights_ = *t.edge_weights();
5636 template <
typename NewVWeight,
typename NewEWeight>
5637 typename wgraph<NewVWeight, NewEWeight>::value
5638 convert_weight_types()
const {
5640 !edge_weights_.has_value(),
5641 "wgraph: value: cannot convert weight type after "
5642 "assigning weights");
5644 return copy_without_weights<NewVWeight, NewEWeight>();
5648 int n()
const {
return n_; }
5651 int m()
const {
return static_cast<
int>(edges_.size()); }
5667 return vertex_weights_;
5672 return edge_weights_;
5677 template <
typename NewVWeight = VWeight>
5679 const std::vector<NewVWeight> &vertex_weights)
const {
5681 "wgraph: value: must give `n` vertex weights");
5683 auto new_graph = copy_without_weights<NewVWeight, EWeight>();
5684 new_graph.edge_weights_ = edge_weights_;
5685 new_graph.vertex_weights_ = vertex_weights;
5691 template <
typename NewEWeight = EWeight>
5695 "wgraph: value: must give `m` edge weights");
5697 auto new_graph = copy_without_weights<VWeight, NewEWeight>();
5698 new_graph.vertex_weights_ = vertex_weights_;
5699 new_graph.edge_weights_ = edge_weights;
5707 "wgraph: value: edge_weighted requires a graph with no "
5710 "wgraph: value: graph is already edge-weighted");
5712 edge_weights_ = std::vector<EWeight>();
5720 print_1_based_ =
true;
5741 std::vector<
int> new_label(
n());
5742 std::vector<
int> shuffled;
5743 for (
int i = 0; i <
n(); ++i) {
5744 if (indices.count(i))
5747 shuffled.push_back(i);
5749 std::vector<
int> targets = shuffled;
5750 tgen::shuffle(targets.begin(), targets.end());
5751 for (size_t k = 0; k < shuffled.size(); ++k)
5752 new_label[shuffled[k]] = targets[k];
5755 std::vector<std::set<
int>> new_adj(
n());
5756 for (
int u = 0; u < n(); ++u)
5757 for (
int v : adj_[u])
5758 new_adj[new_label[u]].insert(new_label[v]);
5762 for (
auto &[u, v] : edges_) {
5765 if (!is_directed_
and u > v)
5770 if (vertex_weights_.has_value()) {
5771 std::vector<VWeight> new_vw(
n());
5772 for (
int i = 0; i < n(); ++i)
5773 new_vw[new_label[i]] = (*vertex_weights_)[i];
5774 vertex_weights_ = new_vw;
5779 std::vector<
int> perm(edges_.size());
5780 std::iota(perm.begin(), perm.end(), 0);
5781 tgen::shuffle(perm.begin(), perm.end());
5783 std::vector<std::pair<
int,
int>> new_edges;
5784 std::optional<std::vector<EWeight>> new_ew;
5785 if (edge_weights_.has_value())
5786 new_ew = std::vector<EWeight>();
5787 for (
int i : perm) {
5788 new_edges.push_back(edges_[i]);
5789 if (new_ew.has_value())
5790 new_ew->push_back((*edge_weights_)[i]);
5794 if (new_ew.has_value())
5795 edge_weights_ = new_ew;
5808 new_vertex_weights = std::nullopt) {
5812 "wgraph: value: number of added vertices must be nonnegative");
5813 tgen_ensure(k <= std::numeric_limits<
int>::max() -
5814 static_cast<
long long>(n_),
5815 "wgraph: value: too many vertices");
5816 if (new_vertex_weights.has_value()) {
5818 "wgraph: value: cannot add weighted vertices to "
5819 "vertex-unweighted graph");
5821 static_cast<
int>(new_vertex_weights->size()) == k,
5822 "wgraph: value: number of vertex weights must be equal "
5823 "to number of added vertices");
5826 "wgraph: value: cannot add unweighted vertices to "
5827 "vertex-weighted graph");
5832 if (new_vertex_weights.has_value())
5833 vertex_weights_->insert(vertex_weights_->end(),
5834 new_vertex_weights->begin(),
5835 new_vertex_weights->end());
5845 "wgraph: value: vertex ids must be valid");
5850 if (adj_[u].count(v))
5855 if (w.has_value()) {
5857 "wgraph: value: cannot add weighted edge to "
5858 "edge-unweighted graph");
5861 "wgraph: value: cannot add unweighted edge to "
5862 "edge-weighted graph");
5867 edges_.emplace_back(u, v);
5869 edge_weights_->push_back(*w);
5879 std::optional<EWeight> new_w = std::nullopt) {
5888 "wgraph: value: vertex ids must be valid");
5892 "wgraph: value: graphs must have the same is_directed value");
5896 add_vertices(rhs.n(), rhs.vertex_weights());
5897 for (
int i = 0; i < rhs
.m(); ++i) {
5898 auto [u, v] = rhs.edges()[i];
5900 rhs.edge_weights().has_value()
5901 ? std::optional<EWeight>((*rhs.edge_weights())[i])
5916 std::set<std::pair<
int,
int>> index_pairs) {
5921 return glue(copy, std::move(index_pairs));
5926 "wgraph: value: graphs must have the same is_directed value");
5929 std::set<
int> idx_left, idx_right;
5930 std::vector<
int> right_id_to_left(rhs
.n(), -1);
5931 for (
auto [l, r] : index_pairs) {
5933 0 <= l
and l < n()
and 0 <= r
and r < rhs.n(),
5934 "wgraph: value: vertex indices to glue must be valid");
5935 tgen_ensure(idx_left.count(l) == 0
and idx_right.count(r) == 0,
5936 "wgraph: value: must not have repeated indices "
5937 "on the same side to glue");
5940 idx_right.insert(r);
5941 right_id_to_left[r] = l;
5945 std::vector<
int> new_right_id(rhs
.n(), -1);
5946 int intersection_lt = 0;
5947 std::optional<std::vector<VWeight>> rhs_vertex_weights;
5949 if (rhs.vertex_weights().has_value())
5950 rhs_vertex_weights = std::vector<VWeight>();
5951 for (
int i = 0; i < rhs
.n(); ++i) {
5952 if (right_id_to_left[i] != -1) {
5955 new_right_id[i] = right_id_to_left[i];
5958 new_right_id[i] =
n() + i - intersection_lt;
5959 if (rhs.vertex_weights().has_value()) {
5960 rhs_vertex_weights->push_back(
5961 (*rhs.vertex_weights())[i]);
5967 add_vertices(rhs.n() - intersection_lt, rhs_vertex_weights);
5968 for (
int i = 0; i < rhs
.m(); ++i) {
5969 auto [u, v] = rhs.edges()[i];
5971 rhs.edge_weights().has_value()
5972 ? std::optional<EWeight>((*rhs.edge_weights())[i])
5979 std::initializer_list<std::pair<
int,
int>> il) {
5980 return glue(rhs, std::set<std::pair<
int,
int>>(il));
5988 std::set<std::pair<
int,
int>> index_pairs;
5989 for (
auto i : indices)
5990 index_pairs.emplace(i, i);
5991 return glue(rhs, index_pairs);
5993 value &glue(
const value &rhs,
const std::initializer_list<
int> &il) {
5994 return glue(rhs, std::set<
int>(il));
6001 return glue(rhs, std::set<
int>());
6008 "wgraph: value: number of edges must be nonnegative");
6011 "wgraph: value: can choose at most `m` edges from graph");
6013 std::vector<std::pair<
int,
int>> new_edges;
6014 std::optional<std::vector<EWeight>> new_edge_weights;
6016 if (edge_weights_.has_value())
6017 new_edge_weights = std::vector<EWeight>();
6020 for (
int i = 0; i <
m(); ++i) {
6021 if (next(1, left--) <= num_edges) {
6022 new_edges.push_back(edges()[i]);
6023 if (edge_weights_.has_value()) {
6024 new_edge_weights->push_back((*edge_weights())[i]);
6031 edge_weights_ = new_edge_weights;
6032 rebuild_adj_from_edge_list();
6044 "wgraph: value: random_connected_subgraph is only for "
6045 "undirected graphs");
6048 "wgraph: value: can choose at most `m` edges from graph");
6052 std::vector<std::vector<std::pair<
int,
int>>> incident(
n());
6053 for (
int i = 0; i <
m(); ++i) {
6054 auto [u, v] = edges_[i];
6055 incident[u].emplace_back(v, i);
6056 incident[v].emplace_back(u, i);
6060 std::vector<
bool> vis(
n(),
false);
6061 std::vector<
int> queue;
6062 std::vector<
bool> in_tree(
m(),
false);
6063 int forest_edges = 0;
6065 for (
int start = 0; start <
n(); ++start) {
6069 queue.push_back(start);
6071 while (!queue.empty()) {
6073 tgen::next<
int>(0,
static_cast<
int>(queue.size()) - 1);
6075 std::swap(queue[i], queue.back());
6078 for (
auto [v, edge_idx] : incident[u]) {
6082 in_tree[edge_idx] =
true;
6089 num_edges >= forest_edges,
6090 "wgraph: value: random_connected_subgraph needs at least "
6091 "`n - c` edges, where `c` is the number of connected "
6095 std::vector<
int> tree_idx, rest_idx;
6096 for (
int i = 0; i <
m(); ++i) {
6098 tree_idx.push_back(i);
6100 rest_idx.push_back(i);
6103 tgen::shuffle(rest_idx.begin(), rest_idx.end());
6105 std::vector<
int> chosen_idx;
6106 chosen_idx.insert(chosen_idx.end(), tree_idx.begin(),
6108 chosen_idx.insert(chosen_idx.end(), rest_idx.begin(),
6109 rest_idx.begin() + num_edges - forest_edges);
6111 detail::tgen_ensure_against_bug(
6112 static_cast<
int>(chosen_idx.size()) == num_edges,
6113 "wgraph: value: chose a wrong number of edges");
6115 std::vector<std::pair<
int,
int>> new_edges;
6116 std::optional<std::vector<EWeight>> new_edge_weights;
6117 if (edge_weights_.has_value())
6118 new_edge_weights = std::vector<EWeight>();
6119 for (
int i : chosen_idx) {
6120 new_edges.push_back(edges_[i]);
6121 if (new_edge_weights.has_value())
6122 new_edge_weights->push_back((*edge_weights_)[i]);
6126 edge_weights_ = new_edge_weights;
6127 rebuild_adj_from_edge_list();
6135 "wgraph: value: cannot compute complement of "
6136 "edge-weighted graph");
6138 value complement = *
this;
6139 complement.ensure_adj_built();
6140 std::vector<std::pair<
int,
int>> compl_edges;
6141 for (
int i = 0; i < complement.n_; ++i) {
6142 std::set<
int> complement_adj;
6143 for (
int j = 0; j < complement.n_; ++j) {
6145 if (j == i
and complement.adj_[i].count(j))
6147 if (j != i
and !complement.adj_[i].count(j))
6151 complement_adj.insert(j);
6153 if (i <= j
or complement.is_directed_) {
6154 compl_edges.emplace_back(i, j);
6158 std::swap(complement.adj_[i], complement_adj);
6160 std::swap(complement.edges_, compl_edges);
6169 "wgraph: value: graphs must have the same "
6170 "is_directed value");
6173 rhs.vertex_weights().has_value(),
6174 "wgraph: value: cannot concatenate vertex-weighted "
6175 "wgraph to unweighted");
6177 rhs.edge_weights().has_value(),
6178 "wgraph: value: cannot concatenate edge-weighted "
6179 "wgraph to unweighted");
6181 value concat = *
this;
6182 concat.glue(rhs, std::set<std::pair<
int,
int>>());
6183 concat.print_1_based_ = print_1_based_ | rhs.print_1_based_;
6184 concat.print_nm_ = print_nm_ | rhs.print_nm_;
6191 friend std::ostream &operator<<(std::ostream &out,
const value &val) {
6194 out << val.n() <<
" " << val.m() <<
'\n';
6197 if (val.vertex_weights()) {
6198 for (
int i = 0; i < val.n(); ++i) {
6201 out << (*val.vertex_weights())[i];
6207 for (
int i = 0; i < val.m(); ++i) {
6208 auto [u, v] = val.edges()[i];
6209 out << (u + val.print_1_based_) <<
" "
6210 << (v + val.print_1_based_);
6213 if (val.edge_weights().has_value())
6214 out <<
" " << (*val.edge_weights())[i];
6226 return std_type(n_, m(), adj_);
6234 std::vector<std::set<
int>> adj(n_ + 1);
6235 for (
int u = 0; u < n_; ++u)
6236 for (
int v : adj_[u])
6237 adj[u + 1].insert(v + 1);
6238 return std_type(n_,
m(), adj);
6245 template <
typename NewVWeight,
typename NewEWeight>
6246 typename wgraph<NewVWeight, NewEWeight>::value
6247 copy_without_weights()
const {
6248 using new_value =
typename wgraph<NewVWeight, NewEWeight>::value;
6249 new_value new_graph =
6250 adj_built_ ? new_value(adj_, is_directed_)
6251 : new_value(n_, std::vector<std::pair<
int,
int>>(),
6253 new_graph.edges_ = edges_;
6254 new_graph.print_1_based_ = print_1_based_;
6255 new_graph.print_nm_ = print_nm_;
6262 void rebuild_adj_from_edge_list()
const {
6263 adj_.assign(n_, {});
6264 for (
auto [u, v] : edges_) {
6274 void ensure_adj_built()
const {
6277 rebuild_adj_from_edge_list();
6285 "wgraph: graphs must have the same is_directed value");
6287 for (
auto [u, v] : rhs.edges())
6297 detail::tgen_ensure_against_bug(
static_cast<
int>(edges_.size()) <= m_,
6298 "wgraph: too many edges were added");
6301 if (
static_cast<
int>(edges_.size()) == m_)
6302 return value(n_, edges_, is_directed_);
6307 if (
auto indexed = try_gen_by_edge_index())
6311 return gen_remaining_edges(
6312 std::vector<std::pair<
int,
int>>(edges_.begin(), edges_.end()));
6322 "wgraph: get_connected is only for undirected graphs");
6324 "wgraph: connected graph needs at least n - 1 edges");
6326 std::vector<std::pair<
int,
int>> edges;
6329 if (edges_.empty()) {
6331 std::vector<
int> prufer(n_ - 2);
6332 for (
int i = 0; i < n_ - 2; ++i)
6333 prufer[i] = next<
int>(0, n_ - 1);
6334 for (
auto [u, v] : detail::edges_from_prufer(std::move(prufer)))
6335 edges.emplace_back(u, v);
6338 edges.assign(edges_.begin(), edges_.end());
6340 std::vector<std::vector<
int>> adj(n_);
6341 for (
auto [u, v] : edges_) {
6342 adj[u].push_back(v);
6343 adj[v].push_back(u);
6346 std::vector<
int> comp_size;
6347 std::vector<std::vector<
int>> component_ids;
6348 std::vector<
bool> vis(n_,
false);
6351 for (
int i = 0; i < n_; ++i) {
6357 comp_size.push_back(0);
6358 component_ids.emplace_back();
6363 component_ids.back().push_back(u);
6364 for (
int v : adj[u]) {
6373 if (component_ids.size() > 1) {
6374 std::vector<
int> prufer_values = many_by_distribution(
6375 static_cast<
int>(component_ids.size()) - 2, comp_size);
6377 detail::edges_from_prufer(std::move(prufer_values)))
6378 edges.emplace_back(pick(component_ids[u]),
6379 pick(component_ids[v]));
6383 return gen_remaining_edges(std::move(edges));
6396 "wgraph: get_acyclic is only for directed graphs");
6398 if (edges_.empty()) {
6399 std::vector<
int> order(n_);
6400 std::iota(order.begin(), order.end(), 0);
6401 for (
int i = n_ - 1; i > 0; --i)
6402 std::swap(order[i], order[next(0, i)]);
6404 const long long max_pairs =
6405 static_cast<
long long>(n_) * (n_ - 1) / 2;
6407 "wgraph: not enough edges to generate");
6409 std::vector<std::pair<
int,
int>> edges;
6411 for (
long long idx : distinct_range<
long long>(0, max_pairs - 1)
6414 auto [i, j] = detail::decode_undirected_simple_edge(n_, idx);
6415 edges.emplace_back(order[i], order[j]);
6417 return value(n_, edges,
true);
6420 std::vector<std::vector<
int>> adj(n_);
6421 std::vector<
int> indeg(n_, 0);
6422 for (
auto [u, v] : edges_) {
6423 adj[u].push_back(v);
6427 std::vector<
int> available;
6428 for (
int i = 0; i < n_; ++i)
6430 available.push_back(i);
6433 std::vector<
int> order;
6434 while (!available.empty()) {
6435 int idx = next(0,
static_cast<
int>(available.size()) - 1);
6436 int u = available[idx];
6437 std::swap(available[idx], available.back());
6438 available.pop_back();
6441 for (
int v : adj[u])
6442 if (--indeg[v] == 0)
6443 available.push_back(v);
6447 "wgraph: preset edges contain a directed cycle");
6449 value acyclic(n_, edges_,
true);
6453 detail::tgen_ensure_against_bug(acyclic.m() <= m_,
6454 "wgraph: too many edges were added");
6456 if (acyclic.m() < m_) {
6457 std::vector<
int> order_pos(n_);
6458 for (
int i = 0; i < n_; ++i)
6459 order_pos[order[i]] = i;
6461 std::unordered_set<uint64_t> seen;
6462 seen.reserve(m_ * 2);
6463 for (
auto [u, v] : acyclic.edges())
6465 detail::undirected_edge_key(order_pos[u], order_pos[v]));
6467 const long long max_pairs =
6468 static_cast<
long long>(n_) * (n_ - 1) / 2;
6469 while (acyclic.m() < m_) {
6470 std::pair<
int,
int> edge;
6471 if (!detail::try_generate_distinct(seen, [&] {
6472 long long idx = next<
long long>(0, max_pairs - 1);
6473 edge = detail::decode_undirected_simple_edge(n_, idx);
6474 return detail::undirected_edge_key(edge.first,
6477 throw detail::error(
"wgraph: not enough edges to generate");
6478 acyclic.add_edge(order[edge.first], order[edge.second]);
6497 bool is_directed =
false) {
6498 tgen_ensure(n > 0,
"wgraph: number of vertices must be positive");
6501 "wgraph: skewed graph needs at least n - 1 edges to be connected");
6503 "wgraph: gen_skewed spread must be at least 2");
6505 value skewed(n, {}, is_directed);
6507 std::vector<
int> parent(n), depth(n, 0);
6509 for (
int i = 1; i < n; ++i) {
6510 int p = wnext<
int>(i, elongation);
6512 depth[i] = depth[p] + 1;
6513 skewed.add_edge(p, i);
6516 const int extra = m - (n - 1);
6523 constexpr int naive_ancestor_spread = 20;
6525 if (spread <= naive_ancestor_spread) {
6526 std::vector<std::pair<
int,
int>> candidates;
6527 candidates.reserve(n * spread);
6528 for (
int u = 0; u < n; ++u) {
6529 int max_k = std::min(spread, depth[u]);
6533 for (
int k = 2; k <= max_k; ++k) {
6535 candidates.emplace_back(v, u);
6539 tgen_ensure(extra <=
static_cast<
int>(candidates.size()),
6540 "wgraph: not enough edges to generate");
6542 for (
auto [v, u] : choose(candidates, extra))
6543 skewed.add_edge(v, u);
6547 while ((1 << lg) <= n)
6550 std::vector<std::vector<
int>> up(lg, std::vector<
int>(n));
6551 for (
int v = 0; v < n; ++v)
6552 up[0][v] = parent[v];
6553 for (
int j = 1; j < lg; ++j)
6554 for (
int v = 0; v < n; ++v)
6555 up[j][v] = up[j - 1][up[j - 1][v]];
6559 std::vector<
int> distribution = depth;
6560 for (
int &d : distribution)
6561 d = std::max(0, std::min(spread - 1, d - 1));
6563 distinct extra_edges([&]() -> std::pair<
int,
int> {
6564 int u =
static_cast<
int>(vertex_choice.next());
6567 int k = next(2, std::min(spread, depth[u]));
6569 for (
int j = 0; j < lg; ++j)
6575 while (skewed.m() < m) {
6576 std::pair<
int,
int> edge;
6578 edge = extra_edges.gen();
6579 }
catch (
const std::runtime_error &e) {
6580 if (std::string(e.what()) ==
6581 "tgen: distinct: no more distinct values")
6582 throw detail::error(
6583 "wgraph: not enough edges to generate");
6587 skewed.add_edge(edge.first, edge.second);
6601 tgen_ensure(m >= 0,
"wgraph: number of edges must be nonnegative");
6602 long long num_edges = 1LL * n1 * n2;
6604 "wgraph: bipartite graph has at most n1 * n2 edges");
6608 "wgraph: connected bipartite graph needs at least n1 + n2 - 1 "
6613 std::vector<std::pair<
int,
int>> edges;
6615 for (
long long idx : distinct_range<
long long>(0, num_edges - 1)
6618 edges.emplace_back(
static_cast<
int>(idx / n2),
6619 n1 +
static_cast<
int>(idx % n2));
6620 return value(n1 + n2, std::move(edges),
false);
6623 std::unordered_set<uint64_t> used_edges;
6624 used_edges.reserve(m * 2);
6625 std::vector<std::pair<
int,
int>> edges;
6628 auto pack_edge = [](
int u,
int v) -> uint64_t {
6631 return (
static_cast<uint64_t>(u) << 32) |
static_cast<uint32_t>(v);
6635 if (n1 > 0
and n2 > 0) {
6636 std::vector<
int> left = {next(0, n1 - 1)};
6637 std::vector<
int> right = {next(n1, n1 + n2 - 1)};
6638 std::vector<
int> remaining;
6641 remaining.reserve(n1 + n2 - 2);
6643 for (
int u = 0; u < n1; ++u)
6645 remaining.push_back(u);
6646 for (
int v = n1; v < n1 + n2; ++v)
6648 remaining.push_back(v);
6649 shuffle(remaining.begin(), remaining.end());
6651 auto add_tree_edge = [&](
int u,
int v) {
6652 used_edges.insert(pack_edge(u, v));
6653 edges.emplace_back(u, v);
6655 add_tree_edge(left[0], right[0]);
6657 for (
int vertex : remaining) {
6659 add_tree_edge(vertex, pick(right));
6660 left.push_back(vertex);
6662 add_tree_edge(pick(left), vertex);
6663 right.push_back(vertex);
6666 detail::tgen_ensure_against_bug(
6667 used_edges.size() == size_t(n1 + n2 - 1),
6668 "wgraph: invalid bipartite spanning tree size");
6672 while (edges.size() < size_t(m)) {
6673 int u = next(0, n1 - 1);
6674 int v = next(n1, n1 + n2 - 1);
6675 if (used_edges.insert(pack_edge(u, v)).second)
6676 edges.emplace_back(u, v);
6679 return value(n1 + n2, std::move(edges),
false);
6688 bool has_self_loops =
false) {
6689 tgen_ensure(n > 0,
"wgraph: number of vertices must be positive");
6690 tgen_ensure(p >= 0
and p <= 1,
"wgraph: probability must be in [0, 1]");
6692 long long max_edges =
6693 detail::max_graph_edges(n, is_directed, has_self_loops);
6699 for (
long long i = 0; i < max_edges; ++i)
6700 if (next<
double>(0.0, 1.0) < p)
6704 "wgraph: too many edges to generate");
6705 return wgraph(n,
static_cast<
int>(m), is_directed, has_self_loops)
6715 std::optional<
value> try_gen_by_edge_index()
const {
6716 if (!edges_.empty())
6717 return std::nullopt;
6719 long long max_edges =
6720 detail::max_graph_edges(n_, is_directed_, has_self_loops_);
6722 throw detail::error(
"wgraph: not enough edges to generate");
6723 if (max_edges <= 0
or 2LL * m_ <= max_edges)
6724 return std::nullopt;
6726 std::vector<std::pair<
int,
int>> edges;
6728 for (
long long idx :
6729 distinct_range<
long long>(0, max_edges - 1).gen_list(m_).to_std())
6730 edges.push_back(detail::decode_graph_edge_index(
6731 n_, idx, is_directed_, has_self_loops_));
6733 return value(n_, edges, is_directed_);
6739 value gen_remaining_edges(std::vector<std::pair<
int,
int>> edges)
const {
6740 detail::tgen_ensure_against_bug(
static_cast<
int>(edges.size()) <= m_,
6741 "wgraph: too many edges were added");
6743 if (
static_cast<
int>(edges.size()) == m_)
6744 return value(n_, edges, is_directed_);
6748 std::unordered_set<uint64_t> seen;
6749 seen.reserve(m_ * 2);
6750 for (
auto [u, v] : edges) {
6751 if (!is_directed_
and u > v)
6753 seen.insert(is_directed_ ? detail::directed_edge_key(u, v)
6754 : detail::undirected_edge_key(u, v));
6757 while (
static_cast<
int>(edges.size()) < m_) {
6758 std::pair<
int,
int> edge;
6759 if (!detail::try_generate_distinct(seen, [&] {
6760 edge = detail::get_random_graph_edge(n_, is_directed_,
6762 if (!is_directed_
and edge.first > edge.second)
6763 std::swap(edge.first, edge.second);
6764 return is_directed_ ? detail::directed_edge_key(edge.first,
6766 : detail::undirected_edge_key(
6767 edge.first, edge.second);
6769 throw detail::error(
"wgraph: not enough edges to generate");
6770 edges.emplace_back(edge);
6773 return value(n_, edges, is_directed_);
6779template <
typename VWeight,
typename EWeight>
6781 const typename wgraph<VWeight, EWeight>::value &g)
6782 : n_(g.n()),
adj_(
g.
n()), print_1_based_(
false), print_n_(
false),
6784 tgen_ensure(g.n() > 0,
"wtree: value: graph must have at least one vertex");
6786 "wtree: value: graph must be undirected to form a tree");
6788 if (g.vertex_weights().has_value())
6789 vertex_weights_ = *g.vertex_weights();
6790 if (g.edge_weights().has_value())
6791 edge_weights_ = std::vector<EWeight>();
6796 std::vector<
int> order(g.m());
6797 std::iota(order.begin(), order.end(), 0);
6798 tgen::shuffle(order.begin(), order.end());
6800 std::vector<std::pair<
int,
int>> tree_edges;
6801 tree_edges.reserve(n_ - 1);
6803 for (
int i : order) {
6804 auto [u, v] = g.edges()[i];
6805 if (!dsu_.unite(u, v))
6810 tree_edges.emplace_back(u, v);
6813 if (edge_weights_.has_value())
6814 edge_weights_->push_back((*g.edge_weights())[i]);
6815 if (
static_cast<
int>(tree_edges.size()) == n_ - 1)
6819 tgen_ensure(
static_cast<
int>(tree_edges.size()) == n_ - 1,
6820 "wtree: value: graph must be connected to form a tree");
6822 edges_ = std::move(tree_edges);
6826
6827
6839
6840
6845 tgen_ensure(n > 0,
"K: number of vertices must be positive");
6847 long long edges = detail::max_graph_edges(n,
false,
false);
6848 tgen_ensure(edges <= std::numeric_limits<
int>::max(),
6849 "K: too many edges to generate");
6850 return graph(n,
static_cast<
int>(edges)).gen();
6858 graph g(n, n - 1, is_directed);
6859 for (
int i = 0; i + 1 < n; ++i)
6860 g.add_edge(i, i + 1);
6869 tgen_ensure(n >= 3,
"graph: cycle size must be at least 3");
6871 graph g(n, n, is_directed);
6872 for (
int i = 0; i < n; ++i)
6873 g.add_edge(i, (i + 1) % n);
6882 graph g(n1 + n2,
static_cast<
long long>(n1) * n2);
6883 for (
int i = 0; i < n1; ++i)
6884 for (
int j = 0; j < n2; ++j)
6885 g.add_edge(i, n1 + j);
6895
6896
6897
6898
6904 static_assert(std::is_arithmetic_v<T>,
6905 "point requires an arithmetic coordinate type");
6917 point(T x = 0, T y = 0) : x_(x), y_(y) {}
6920 T
x()
const {
return x_; }
6923 T
y()
const {
return y_; }
6926 static bool coord_eq(T a, T b) {
return a == b; }
6930 if (!coord_eq(x_, p
.x()))
6937 return coord_eq(x_, p
.x())
and coord_eq(y_, p
.y());
6955 if constexpr (std::is_floating_point_v<T>) {
6960 product_t x_product, y_product, result;
6962 "geometry: point dot product overflow");
6963 tgen_ensure(!__builtin_mul_overflow(y_, p.y(), &y_product),
6964 "geometry: point dot product overflow");
6965 tgen_ensure(!__builtin_add_overflow(x_product, y_product, &result),
6966 "geometry: point dot product overflow");
6973 if constexpr (std::is_floating_point_v<T>)
6977 product_t x_product, y_product, result;
6979 "geometry: point cross product overflow");
6980 tgen_ensure(!__builtin_mul_overflow(y_, p.x(), &y_product),
6981 "geometry: point cross product overflow");
6982 tgen_ensure(!__builtin_sub_overflow(x_product, y_product, &result),
6983 "geometry: point cross product overflow");
6989 friend std::ostream &operator<<(std::ostream &out,
const point &p) {
6990 return out << p
.x() <<
' ' << p
.y();
6999 long long max_coord) {
7001 "geometry: random_points_general_position: n must be positive");
7003 "geometry: random_points_general_position: min_coord must be "
7004 "at most max_coord");
7006 static_cast<detail::i128>(max_coord) - min_coord <=
7007 std::numeric_limits<
long long>::max(),
7008 "geometry: random_points_general_position: coordinate range too large");
7009 uint64_t width = max_coord - min_coord;
7011 tgen_ensure(n <= std::numeric_limits<
int>::max() / 2,
7012 "geometry: random_points_general_position: n too large");
7014 tgen_ensure(p - 1 <=
static_cast<uint64_t>(std::numeric_limits<
int>::max()),
7015 "geometry: random_points_general_position: n too large");
7019 "geometry: random_points_general_position: coordinate range "
7028 std::vector<uint64_t> x_range(p - 1);
7029 std::iota(x_range.begin(), x_range.end(), uint64_t{1});
7030 shuffle(x_range.begin(), x_range.end());
7031 std::vector<detail::i128> bx(n), by(n);
7032 for (
int i = 0; i < n; ++i) {
7033 uint64_t x = x_range[i];
7035 by[i] = math::modular_inverse(x, p);
7043 const int num_shears = 8;
7044 std::vector<detail::i128> lin_x = bx, lin_y = by;
7046 for (
int it = 0; it < num_shears; ++it) {
7047 bool vertical_shear = next(2) == 0;
7048 int shear_r = pick({-2, -1, 1, 2});
7050 for (
int i = 0; i < n; ++i) {
7052 lin_x[i] = (lin_x[i] + shear_r * lin_y[i]) % p;
7054 lin_y[i] = (lin_y[i] + shear_r * lin_x[i]) % p;
7063 detail::i128 min_x = lin_x[0], max_x = lin_x[0], min_y = lin_y[0],
7065 for (
int i = 1; i < n; ++i) {
7066 min_x = std::min(min_x, lin_x[i]);
7067 max_x = std::max(max_x, lin_x[i]);
7068 min_y = std::min(min_y, lin_y[i]);
7069 max_y = std::max(max_y, lin_y[i]);
7072 detail::i128 x_shift =
7074 next<uint64_t>(0,
static_cast<uint64_t>(width - (max_x - min_x)));
7075 detail::i128 y_shift =
7077 next<uint64_t>(0,
static_cast<uint64_t>(width - (max_y - min_y)));
7079 std::vector<point<
long long>> pts;
7080 for (
int i = 0; i < n; ++i)
7081 pts.emplace_back(
static_cast<
long long>(lin_x[i] + x_shift),
7082 static_cast<
long long>(lin_y[i] + y_shift));
7088using i128 = tgen::detail::i128;
7090using u128 = tgen::detail::u128;
7099inline signed_area triangle_area(
const point<
long long> &a,
7100 const point<
long long> &b,
7101 const point<
long long> &p) {
7102 i128 dx1 = i128(b.x()) - a.x(), dy1 = i128(b.y()) - a.y();
7103 i128 dx2 = i128(p.x()) - a.x(), dy2 = i128(p.y()) - a.y();
7104 auto magnitude = [](i128 v) -> u128 {
return v < 0 ? -v : v; };
7105 u128 first = magnitude(dx1) * magnitude(dy2);
7106 u128 second = magnitude(dy1) * magnitude(dx2);
7107 int first_sign = (dx1 < 0) != (dy2 < 0) ? -1 : 1;
7108 int second_sign = (dy1 < 0) != (dx2 < 0) ? -1 : 1;
7109 if (first_sign != second_sign) {
7112 u128 sum = first + second;
7113 return {sum, sum == 0 ? 0 : first_sign};
7115 if (first == second)
7117 return first > second ? signed_area{first - second, first_sign}
7118 : signed_area{second - first, -first_sign};
7122inline int ccw(
const point<
long long> &a,
const point<
long long> &b,
7123 const point<
long long> &p) {
7124 return triangle_area(a, b, p).sign;
7130inline int compare_weighted_areas(u128 x, uint64_t a, u128 y, uint64_t b) {
7131 u128 qx = x / b, qy = y / a;
7133 return qx > qy ? 1 : -1;
7134 u128 rx = (x % b) * a, ry = (y % a) * b;
7135 return (rx > ry) - (rx < ry);
7141inline bool split_on_positive_side(
const point<
long long> &A,
7142 const point<
long long> &B,
7143 const point<
long long> &C,
7144 const point<
long long> &P, uint64_t wa,
7146 signed_area a = triangle_area(C, A, P), b = triangle_area(C, B, P);
7149 if (b.sign == 0
or a.sign == b.sign)
7151 int comparison = compare_weighted_areas(a.magnitude, wa, b.magnitude, wb);
7152 return comparison == 0 ? b.sign > 0 : comparison == a.sign;
7159inline void conquer(std::vector<point<
long long>> &points,
int left,
7161 if (right - left <= 3)
7164 point<
long long> A = points[left], B = points[right - 1];
7167 bool all_collinear =
true;
7168 for (
int k = left + 1; k < right - 1; ++k) {
7169 if (ccw(A, B, points[k]) != 0) {
7170 all_collinear =
false;
7174 if (all_collinear) {
7175 std::sort(points.begin() + left, points.begin() + right,
7176 [&](
const point<
long long> &P,
const point<
long long> &Q) {
7177 return A < B ? P < Q : Q < P;
7183 std::vector<
int> candidates;
7184 for (
int k = left + 1; k < right - 1; ++k) {
7185 if (ccw(A, B, points[k]) != 0)
7186 candidates.push_back(k);
7188 int ci = candidates[next(0,
static_cast<
int>(candidates.size()) - 1)];
7189 point<
long long> C = points[ci];
7191 uint64_t wa = next<uint64_t>(1, std::numeric_limits<uint64_t>::max());
7192 uint64_t wb = next<uint64_t>(1, std::numeric_limits<uint64_t>::max());
7193 bool a_on_positive = ccw(C, A, B) < 0;
7196 auto is_positive = [&](
const point<
long long> &P) ->
bool {
7197 return split_on_positive_side(A, B, C, P, wa, wb);
7202 if (ci != right - 2)
7203 std::swap(points[ci], points[right - 2]);
7208 if (is_positive(points[i]) == a_on_positive)
7210 else if (is_positive(points[j]) != a_on_positive)
7213 std::swap(points[i], points[j]);
7224 if (i == j
and is_positive(points[i]) == a_on_positive)
7226 std::swap(points[p], points[right - 2]);
7229 conquer(points, left, p + 1);
7231 conquer(points, p, right);
7238inline std::vector<
long long>
7239sample_sorted_distinct_in_range(
int k,
long long left,
long long right) {
7240 long long universe = right - left + 1;
7241 std::vector<
long long> res;
7246 constexpr long long pool_threshold = 8'000'000;
7247 constexpr long long pool_always_below = 500'000;
7249 if (universe <= pool_threshold
and
7250 (universe <= pool_always_below
or k >= universe / 4)) {
7251 size_t u = universe;
7253 std::vector<
long long> pool(u);
7254 std::iota(pool.begin(), pool.end(), left);
7255 size_t m = ks <= u / 2 ? ks : u - ks;
7256 for (size_t i = 0; i < m; ++i) {
7257 size_t j = next<size_t>(i, u - 1);
7258 std::swap(pool[i], pool[j]);
7261 res.assign(pool.begin(), pool.begin() + ks);
7262 std::sort(res.begin(), res.end());
7264 std::vector<
char> excluded(u, 0);
7265 for (size_t i = 0; i < m; ++i)
7266 excluded[pool[i] - left] = 1;
7267 for (
long long v = left; v <= right; ++v)
7268 if (!excluded[v - left])
7272 std::unordered_map<
long long,
long long> virtual_list;
7273 virtual_list.reserve(k * 2);
7274 for (
long long i = 0; i < k; ++i) {
7275 long long j = next<
long long>(i, universe - 1);
7276 long long vi = virtual_list.count(i) ? virtual_list[i] : i;
7277 long long vj = virtual_list.count(j) ? virtual_list[j] : j;
7278 virtual_list[j] = vi;
7279 virtual_list[i] = vj;
7280 res.push_back(virtual_list[i] + left);
7282 std::sort(res.begin(), res.end());
7289inline std::vector<
long long>
7290valtr_edge_components(
const std::vector<
long long> &sorted_coords) {
7291 int n =
static_cast<
int>(sorted_coords.size());
7292 std::vector<
long long> left, right;
7293 left.reserve(n / 2);
7294 right.reserve(n / 2);
7295 for (
int i = 1; i + 1 < n; ++i) {
7297 left.push_back(sorted_coords[i]);
7299 right.push_back(sorted_coords[i]);
7301 long long lo = sorted_coords.front(), hi = sorted_coords.back();
7302 std::vector<
long long> seq;
7305 for (
long long v : left)
7308 for (
auto it = right.rbegin(); it != right.rend(); ++it)
7311 std::vector<
long long> comps(n);
7312 for (
int i = 0; i < n; ++i)
7313 comps[i] = seq[i + 1] - seq[i];
7319inline std::vector<point<
long long>>
7320simplify_strict_boundary(std::vector<point<
long long>> points) {
7321 int n =
static_cast<
int>(points.size());
7325 std::vector<point<
long long>> strict_points;
7326 strict_points.reserve(n);
7327 for (
int i = 0; i < n; ++i) {
7328 if (ccw(points[(i + n - 1) % n], points[i], points[(i + 1) % n]) != 0)
7329 strict_points.push_back(points[i]);
7331 return strict_points;
7336inline std::vector<point<
long long>>
7337subsample_boundary(
const std::vector<point<
long long>> &points,
int k) {
7338 int n =
static_cast<
int>(points.size());
7342 std::vector<point<
long long>> sampled_points;
7343 sampled_points.reserve(k);
7344 for (
int i = 0; i < k; ++i)
7345 sampled_points.push_back(
7346 points[
static_cast<size_t>((
static_cast<i128>(i) * n) / k)]);
7347 return sampled_points;
7352inline void place_inside_box(std::vector<point<
long long>> &points,
7353 long long min_coord,
long long max_coord) {
7354 long long width = max_coord - min_coord + 1;
7356 i128 min_x = points[0].x(), max_x = points[0].x();
7357 i128 min_y = points[0].y(), max_y = points[0].y();
7358 for (
const point<
long long> &p : points) {
7359 min_x = std::min(min_x,
static_cast<i128>(p.x()));
7360 max_x = std::max(max_x,
static_cast<i128>(p.x()));
7361 min_y = std::min(min_y,
static_cast<i128>(p.y()));
7362 max_y = std::max(max_y,
static_cast<i128>(p.y()));
7365 i128 span_x = max_x - min_x;
7366 i128 span_y = max_y - min_y;
7370 next<
long long>(0, width - 1 -
static_cast<
long long>(span_x));
7373 next<
long long>(0, width - 1 -
static_cast<
long long>(span_y));
7375 for (point<
long long> &p : points)
7376 p = point<
long long>(
static_cast<
long long>(p.x() + shift_x),
7377 static_cast<
long long>(p.y() + shift_y));
7382inline void randomize_cyclic_shift(std::vector<point<
long long>> &points) {
7383 int rot = next(
static_cast<
int>(points.size()));
7385 std::rotate(points.begin(), points.begin() + rot, points.end());
7390inline std::vector<point<
long long>>
7391valtr_vertices(
int m,
const std::vector<
long long> &x_comp,
7392 std::vector<
long long> y_comp) {
7393 shuffle(y_comp.begin(), y_comp.end());
7395 std::vector<point<
long long>> edges(m);
7397 auto upper = [](
const point<
long long> &p) {
7398 return p.y() > 0
or (p.y() == 0
and p.x() > 0);
7400 for (
int i = 0; i < m; ++i)
7401 edges[i] =
point<
long long>(x_comp[i], y_comp[i]);
7403 std::sort(edges.begin(), edges.end(),
7404 [&upper](
const point<
long long> &a,
const point<
long long> &b) {
7405 bool au = upper(a), bu = upper(b);
7411 return (a * a) < (b * b);
7415 i128 cur_x = 0, cur_y = 0;
7416 std::vector<i128> px(m), py(m);
7417 for (
int i = 0; i < m; ++i) {
7420 cur_x += edges[i].x();
7421 cur_y += edges[i].y();
7423 tgen::detail::tgen_ensure_against_bug(
7424 cur_x == 0
and cur_y == 0,
7425 "geometry: random_convex_polygon: walk did not close");
7427 i128 min_x = px[0], min_y = py[0];
7428 for (
int i = 1; i < m; ++i) {
7429 min_x = std::min(min_x, px[i]);
7430 min_y = std::min(min_y, py[i]);
7434 std::vector<point<
long long>> points;
7436 for (
int i = 0; i < m; ++i)
7437 points.emplace_back(px[i] - min_x, py[i] - min_y);
7450 bool strict =
false) {
7452 "geometry: random_convex_polygon: n must be at least 3");
7454 "geometry: random_convex_polygon: min_coord must be at most "
7456 tgen_ensure(
static_cast<detail::i128>(max_coord) - min_coord + 1 <=
7457 std::numeric_limits<
long long>::max(),
7458 "geometry: random_convex_polygon: coordinate range too large");
7459 long long width = max_coord - min_coord + 1;
7462 "geometry: random_convex_polygon: coordinate range too small for n");
7470 int extra = width <= n ? 0
7471 :
static_cast<
int>(std::min<
long long>(
7472 std::max(100, n / 1000), width - n));
7473 num_coords = n + extra;
7478 const int max_attempts = strict ? 32 : 1;
7479 for (
int i = 0; i < max_attempts; ++i) {
7481 std::vector<
long long> x_sorted =
7482 detail::sample_sorted_distinct_in_range(num_coords, 0, width - 1);
7483 std::vector<
long long> y_sorted =
7484 detail::sample_sorted_distinct_in_range(num_coords, 0, width - 1);
7485 std::vector<
long long> x_comp = detail::valtr_edge_components(x_sorted);
7486 std::vector<
long long> y_comp = detail::valtr_edge_components(y_sorted);
7488 std::vector<point<
long long>> points =
7489 detail::valtr_vertices(num_coords, x_comp, std::move(y_comp));
7492 std::vector<point<
long long>> simplified =
7493 detail::simplify_strict_boundary(std::move(points));
7495 if (
static_cast<
int>(simplified.size()) < n)
7498 points = detail::subsample_boundary(simplified, n);
7501 detail::place_inside_box(points, min_coord, max_coord);
7502 detail::randomize_cyclic_shift(points);
7507 throw tgen::detail::error(
7508 "geometry: random_convex_polygon: generation failed: coordinate "
7509 "range too small for n");
7518 const std::vector<point<
long long>> &points) {
7519 int n =
static_cast<
int>(points.size());
7521 "geometry: random_simple_polygon_through_points: need at "
7525 std::set<point<
long long>>(points.begin(), points.end()).size()) ==
7527 "geometry: random_simple_polygon_through_points: points must "
7530 int idx_a = 0, idx_b = 0;
7531 for (
int i = 1; i < n; ++i) {
7532 if (points[i] < points[idx_a])
7534 if (points[idx_b] < points[i])
7537 point<
long long> A = points[idx_a], B = points[idx_b];
7539 bool all_collinear =
true;
7540 for (
int i = 0; i < n; ++i) {
7541 if (i == idx_a
or i == idx_b)
7543 if (detail::ccw(A, B, points[i]) != 0) {
7544 all_collinear =
false;
7549 "geometry: random_simple_polygon_through_points: all points "
7550 "are collinear; no simple polygon exists");
7555 int negative_count = 0;
7556 for (
int i = 0; i < n; ++i) {
7557 if (i == idx_a
or i == idx_b)
7559 if (detail::ccw(A, B, points[i]) < 0)
7563 std::vector<point<
long long>> chain;
7566 for (
int i = 0; i < n; ++i) {
7567 if (i == idx_a
or i == idx_b)
7569 int side = detail::ccw(A, B, points[i]);
7570 if (side < 0
or (side == 0
and negative_count == 0)) {
7571 chain.push_back(points[i]);
7576 for (
int i = 0; i < n; ++i) {
7577 if (i == idx_a
or i == idx_b)
7579 int side = detail::ccw(A, B, points[i]);
7580 if (side > 0
or (side == 0
and negative_count != 0))
7581 chain.push_back(points[i]);
7585 int n1 = 2 + left_count;
7587 detail::conquer(chain, 0, n1);
7589 detail::conquer(chain, n1 - 1,
static_cast<
int>(chain.size()));
7593 std::vector<point<
long long>> poly;
7594 poly.insert(poly.end(), chain.begin() + 1, chain.begin() + n1);
7595 poly.insert(poly.end(), chain.begin() + n1, chain.end());
7603inline std::vector<point<
long long>>
7604random_distinct_points_in_box(
int n,
long long min_coord,
long long max_coord) {
7605 long long width = max_coord - min_coord;
7607 i128 side_128 = i128(width) + 1;
7608 i128 universe = side_128 * side_128;
7609 tgen_ensure(universe <= std::numeric_limits<
long long>::max(),
7610 "geometry: random_simple_polygon: coordinate range too large");
7611 long long side =
static_cast<
long long>(side_128);
7613 "geometry: random_simple_polygon: coordinate range too small "
7614 "for n distinct points");
7617 auto decode = [&](
long long key) ->
point<
long long> {
7618 return point<
long long>(min_coord + key / side, min_coord + key % side);
7624 std::vector<
long long> keys =
7625 distinct_range<
long long>(0,
static_cast<
long long>(universe - 1))
7629 std::vector<point<
long long>> points;
7631 for (
long long key : keys)
7632 points.push_back(decode(key));
7635 for (
int i = 2; i < n; ++i) {
7636 if (ccw(points[0], points[1], points[i]) != 0)
7644struct ortho_poly_edge {
7654inline bool ortho_axis_collinear(
const point<
long long> &a,
7655 const point<
long long> &b,
7656 const point<
long long> &c) {
7657 return (a.x() == b.x()
and b.x() == c.x())
or
7658 (a.y() == b.y()
and b.y() == c.y());
7663inline ortho_poly_edge
7664ortho_analyze_edge(
const std::vector<point<
long long>> &poly,
int i) {
7665 int m =
static_cast<
int>(poly.size());
7666 point<
long long> a = poly[i], b = poly[(i + 1) % m];
7667 ortho_poly_edge e{};
7668 if (a.y() == b.y()) {
7671 e.lo = std::min(a.x(), b.x());
7672 e.hi = std::max(a.x(), b.x());
7674 e.out_y = a.x() < b.x() ? -1 : 1;
7677 e.lo = std::min(a.y(), b.y());
7678 e.hi = std::max(a.y(), b.y());
7679 e.out_x = a.y() < b.y() ? 1 : -1;
7681 e.len = e.hi - e.lo;
7688inline bool ortho_open_seg_cross(
const point<
long long> &a,
7689 const point<
long long> &b,
7690 const point<
long long> &c,
7691 const point<
long long> &d) {
7692 if (a.y() == b.y()
and c.y() == d.y()) {
7695 long long lo1 = std::min(a.x(), b.x()), hi1 = std::max(a.x(), b.x());
7696 long long lo2 = std::min(c.x(), d.x()), hi2 = std::max(c.x(), d.x());
7697 return lo1 < hi2
and lo2 < hi1;
7699 if (a.x() == b.x()
and c.x() == d.x()) {
7702 long long lo1 = std::min(a.y(), b.y()), hi1 = std::max(a.y(), b.y());
7703 long long lo2 = std::min(c.y(), d.y()), hi2 = std::max(c.y(), d.y());
7704 return lo1 < hi2
and lo2 < hi1;
7706 if (a.y() == b.y()
and c.x() == d.x()) {
7707 long long hx = a.y(), vx = c.x();
7708 long long hlo = std::min(a.x(), b.x()), hhi = std::max(a.x(), b.x());
7709 long long vlo = std::min(c.y(), d.y()), vhi = std::max(c.y(), d.y());
7710 return hlo < vx
and vx < hhi
and vlo < hx
and hx < vhi;
7712 if (a.x() == b.x()
and c.y() == d.y()) {
7713 long long vx = a.x(), hy = c.y();
7714 long long vlo = std::min(a.y(), b.y()), vhi = std::max(a.y(), b.y());
7715 long long hlo = std::min(c.x(), d.x()), hhi = std::max(c.x(), d.x());
7716 return vlo < hy
and hy < vhi
and hlo < vx
and vx < hhi;
7723inline bool ortho_point_inside(
const std::vector<point<
long long>> &poly,
7724 point<
long long> p) {
7725 int m =
static_cast<
int>(poly.size());
7726 bool inside =
false;
7727 for (
int i = 0, j = m - 1; i < m; j = i++) {
7728 point<
long long> a = poly[i], b = poly[j];
7729 if ((a.y() > p.y()) != (b.y() > p.y())) {
7730 i128 x_cross = i128(b.x() - a.x()) * (p.y() - a.y()) -
7731 i128(p.x() - a.x()) * (b.y() - a.y());
7732 if ((a.y() < b.y()) ? x_cross > 0 : x_cross < 0)
7741inline bool ortho_point_strictly_interior(
point<
long long> p,
7743 point<
long long> b) {
7744 if (a.y() == b.y()) {
7747 long long lo = std::min(a.x(), b.x()), hi = std::max(a.x(), b.x());
7748 return lo < p.x()
and p.x() < hi;
7750 if (a.x() == b.x()) {
7753 long long lo = std::min(a.y(), b.y()), hi = std::max(a.y(), b.y());
7754 return lo < p.y()
and p.y() < hi;
7761inline bool ortho_point_on_segment(
point<
long long> p,
point<
long long> a,
7762 point<
long long> b) {
7763 return p == a
or p == b
or ortho_point_strictly_interior(p, a, b);
7771inline bool ortho_bump_valid(
const std::vector<point<
long long>> &poly,
7773 const std::vector<point<
long long>> &add,
7774 int edge_i,
bool inward) {
7775 int m =
static_cast<
int>(poly.size());
7777 for (point<
long long> v : add)
7778 for (point<
long long> q : poly)
7784 for (point<
long long> v : add) {
7785 for (
int j = 0; j < m; ++j) {
7786 point<
long long> c = poly[j], d = poly[(j + 1) % m];
7788 if (ortho_point_on_segment(v, c, d)
and
7789 !ortho_point_on_segment(v, A, B))
7791 }
else if (ortho_point_strictly_interior(v, c, d)) {
7797 auto seg_ok = [&](
point<
long long> s0,
point<
long long> s1) {
7798 for (
int j = 0; j < m; ++j) {
7801 point<
long long> c = poly[j], d = poly[(j + 1) % m];
7802 if (ortho_open_seg_cross(s0, s1, c, d))
7805 for (
int k = 0; k < m; ++k) {
7806 point<
long long> q = poly[k];
7807 if (q == s0
or q == s1
or q == A
or q == B)
7809 if (ortho_point_strictly_interior(q, s0, s1))
7815 point<
long long> prev = A;
7816 for (point<
long long> v : add) {
7817 if (!seg_ok(prev, v))
7821 if (!seg_ok(prev, B))
7825 for (point<
long long> v : add)
7826 if (!ortho_point_inside(poly, v))
7836inline bool ortho_bump_edge(std::vector<point<
long long>> &poly,
int edge_i,
7837 const ortho_poly_edge &e,
long long lo,
7838 long long hi,
long long depth,
bool inward,
7839 size_t max_vertices) {
7840 int m =
static_cast<
int>(poly.size());
7841 point<
long long> A = poly[edge_i], B = poly[(edge_i + 1) % m];
7843 int step_x = inward ? -e.out_x : e.out_x;
7844 int step_y = inward ? -e.out_y : e.out_y;
7846 std::vector<point<
long long>> add;
7848 long long y = e.fixed, y2 = y + step_y * depth;
7849 if (A.x() < B.x()) {
7851 add.emplace_back(lo, y);
7852 add.emplace_back(lo, y2);
7853 add.emplace_back(hi, y2);
7855 add.emplace_back(hi, y);
7858 add.emplace_back(hi, y);
7859 add.emplace_back(hi, y2);
7860 add.emplace_back(lo, y2);
7862 add.emplace_back(lo, y);
7865 long long x = e.fixed, x2 = x + step_x * depth;
7866 if (A.y() < B.y()) {
7868 add.emplace_back(x, lo);
7869 add.emplace_back(x2, lo);
7870 add.emplace_back(x2, hi);
7872 add.emplace_back(x, hi);
7875 add.emplace_back(x, hi);
7876 add.emplace_back(x2, hi);
7877 add.emplace_back(x2, lo);
7879 add.emplace_back(x, lo);
7882 if (poly.size() > max_vertices
or add.size() > max_vertices - poly.size())
7884 if (!ortho_bump_valid(poly, A, B, add, edge_i, inward))
7887 poly.insert(poly.begin() + edge_i + 1, add.begin(), add.end());
7894inline int ortho_pick_poly_edge(
const std::vector<point<
long long>> &poly,
7895 std::vector<
int> &last_used,
int &time_stamp) {
7896 int m =
static_cast<
int>(poly.size());
7897 if (last_used.size() !=
static_cast<size_t>(m)) {
7898 last_used.assign(m, 0);
7901 std::vector<
long long> weights(m);
7902 long long total = 0;
7903 for (
int i = 0; i < m; ++i) {
7904 ortho_poly_edge e = ortho_analyze_edge(poly, i);
7905 weights[i] = e.len * (4 + std::min(time_stamp - last_used[i], 8));
7906 total += weights[i];
7908 long long pick = next<
long long>(0, total - 1);
7909 for (
int i = 0; i < m; ++i) {
7912 last_used[i] = ++time_stamp;
7916 last_used[m - 1] = ++time_stamp;
7923ortho_try_bump(std::vector<point<
long long>> &poly,
int n,
7924 std::vector<
int> &last_used,
int &time_stamp,
7925 bool outward_only =
false,
7926 size_t max_vertices = std::numeric_limits<size_t>::max()) {
7927 if (poly.size() < 3)
7930 int ei = ortho_pick_poly_edge(poly, last_used, time_stamp);
7931 ortho_poly_edge e = ortho_analyze_edge(poly, ei);
7938 long long span = next<
long long>(2, e.len);
7939 long long lo = next<
long long>(e.lo, e.hi - span);
7943 long long max_depth =
7944 std::clamp(
static_cast<
long long>(std::sqrt(n) / 2 + 2), 2LL, 12LL);
7946 next(10) == 0 ? next<
long long>(std::max(2LL, max_depth / 2), max_depth)
7947 : next<
long long>(1, std::max(2LL, max_depth / 3));
7949 bool inward = !outward_only
and next(4) == 0;
7950 return ortho_bump_edge(poly, ei, e, lo, lo + span, depth, inward,
7956inline std::vector<point<
long long>>
7957ortho_simplify_collinear(std::vector<point<
long long>> poly) {
7958 int n =
static_cast<
int>(poly.size());
7961 std::vector<point<
long long>> out;
7963 for (
int i = 0; i < n; ++i) {
7964 if (!ortho_axis_collinear(poly[(i + n - 1) % n], poly[i],
7966 out.push_back(poly[i]);
7968 return out.size() >= 3 ? out : poly;
7973inline bool ortho_remove_one_collinear(std::vector<point<
long long>> &poly) {
7974 int n =
static_cast<
int>(poly.size());
7977 for (
int i = 0; i < n; ++i) {
7978 if (!ortho_axis_collinear(poly[(i + n - 1) % n], poly[i],
7981 poly.erase(poly.begin() + i);
7990inline void ortho_fill_collinear(std::vector<point<
long long>> &poly,
7992 int need = target -
static_cast<
int>(poly.size());
7996 std::vector<point<
long long>> out;
7997 int m =
static_cast<
int>(poly.size());
7998 out.reserve(poly.size() + need);
8000 for (
int i = 0; i < m; ++i) {
8001 point<
long long> a = poly[i], b = poly[(i + 1) % m];
8006 ortho_poly_edge e = ortho_analyze_edge(poly, i);
8007 long long cap = e.len - 1;
8012 long long take = std::min<
long long>(need, cap);
8013 bool forward = e.horiz ? a.x() < b.x() : a.y() < b.y();
8014 for (
long long k = 0; k < take; ++k) {
8015 long long off = (k + 1) * (cap + 1) / (take + 1);
8016 long long coord = forward ? e.lo + off : e.hi - off;
8018 out.push_back({coord, e.fixed});
8020 out.push_back({e.fixed, coord});
8022 need -=
static_cast<
int>(take);
8034inline void ortho_fill_corrugation(std::vector<point<
long long>> &poly,
8036 size_t n_sz = poly.size();
8040 size_t extra_left = target - n_sz;
8042 std::vector<point<
long long>> out;
8043 out.reserve(target);
8044 int n =
static_cast<
int>(poly.size());
8046 for (
int i = 0; i < n; ++i) {
8047 point<
long long> a = poly[i], b = poly[(i + 1) % n];
8053 ortho_poly_edge e = ortho_analyze_edge(poly, i);
8057 long long dir = (e.horiz ? a.x() < b.x() : a.y() < b.y()) ? 1 : -1;
8058 long long start = e.horiz ? a.x() : a.y();
8059 long long end = e.horiz ? b.x() : b.y();
8061 for (
long long pos = start + 2 * dir;
8062 extra_left >= 4
and (pos - end) * dir <= -3; pos += 2 * dir) {
8064 long long y2 = e.fixed + e.out_y;
8065 out.push_back({pos, e.fixed});
8066 out.push_back({pos, y2});
8067 out.push_back({pos + dir, y2});
8068 out.push_back({pos + dir, e.fixed});
8070 long long x2 = e.fixed + e.out_x;
8071 out.push_back({e.fixed, pos});
8072 out.push_back({x2, pos});
8073 out.push_back({x2, pos + dir});
8074 out.push_back({e.fixed, pos + dir});
8085inline std::vector<point<
long long>> build_orthogonal_polygon(
int n,
8087 bool scale_up = n > 1000;
8089 long long side = std::max(3LL,
static_cast<
long long>(std::sqrt(n)));
8091 side = std::clamp(
static_cast<
long long>(2 * std::sqrt(std::sqrt(n))),
8093 std::vector<point<
long long>> poly = {
8094 {0, 0}, {side, 0}, {side, side}, {0, side}};
8096 int target_ops = scale_up ? std::max(1,
static_cast<
int>(4 * side - 4) / 2)
8097 : std::max(1, (n - 4) / 2);
8100 target_ops = std::min(
8102 400 +
static_cast<
int>(4 * std::sqrt(
static_cast<
double>(side))));
8104 int failure_limit = std::min(target_ops * 8, 2000);
8106 std::vector<
int> last_used;
8107 int time_stamp = 0, consecutive_failures = 0;
8108 size_t max_vertices =
8109 scale_up ? std::numeric_limits<size_t>::max() :
static_cast<size_t>(n);
8110 for (
int ops = 0; ops < target_ops;) {
8111 if (!scale_up
and poly.size() + 2 >
static_cast<size_t>(n))
8114 if (ortho_try_bump(poly, n, last_used, time_stamp, scale_up,
8117 consecutive_failures = 0;
8118 }
else if (++consecutive_failures >= failure_limit) {
8123 poly = ortho_simplify_collinear(std::move(poly));
8126 while (poly.size() >
static_cast<size_t>(n)
and
8127 ortho_remove_one_collinear(poly))
8129 long long upscale = std::max(
8130 4LL, ((
static_cast<
long long>(n) + 3) / 4 + side - 1) / side);
8131 for (point<
long long> &p : poly)
8132 p = {p.x() * upscale, p.y() * upscale};
8134 ortho_fill_corrugation(poly, n);
8136 ortho_fill_collinear(poly, n);
8138 ortho_fill_collinear(poly, n);
8154 bool strict =
false) {
8156 "geometry: random_simple_polygon: n must be at least 3");
8158 "geometry: random_simple_polygon: min_coord must be at most "
8160 tgen_ensure(
static_cast<detail::i128>(max_coord) - min_coord <=
8161 std::numeric_limits<
long long>::max(),
8162 "geometry: random_simple_polygon: coordinate range too large");
8164 std::vector<point<
long long>> points =
8165 strict ? random_points_general_position(n, min_coord, max_coord)
8166 : detail::random_distinct_points_in_box(n, min_coord, max_coord);
8167 return random_simple_polygon_through_points(points);
8176 bool strict =
false) {
8178 "geometry: random_orthogonal_polygon: n must be at least 4");
8180 "geometry: random_orthogonal_polygon: min_coord must be at "
8182 tgen_ensure(
static_cast<detail::i128>(max_coord) - min_coord + 1 <=
8183 std::numeric_limits<
long long>::max(),
8184 "geometry: random_orthogonal_polygon: coordinate range too "
8186 long long width = max_coord - min_coord + 1;
8188 "geometry: random_orthogonal_polygon: coordinate range too "
8191 long long min_side = std::max(3LL,
static_cast<
long long>(std::sqrt(n)));
8194 std::max<
long long>(min_side, (
static_cast<
long long>(n) + 3) / 4);
8196 "geometry: random_orthogonal_polygon: coordinate range too "
8199 for (
int attempt = 0; attempt < 8; ++attempt) {
8200 std::vector<point<
long long>> poly =
8201 detail::build_orthogonal_polygon(n, strict);
8203 if (!strict
and poly.size() !=
static_cast<size_t>(n))
8206 detail::i128 min_x = poly[0].x(), max_x = poly[0].x();
8207 detail::i128 min_y = poly[0].y(), max_y = poly[0].y();
8208 for (point<
long long> p : poly) {
8209 min_x = std::min(min_x, detail::i128(p.x()));
8210 max_x = std::max(max_x, detail::i128(p.x()));
8211 min_y = std::min(min_y, detail::i128(p.y()));
8212 max_y = std::max(max_y, detail::i128(p.y()));
8214 if (max_x - min_x >= width
or max_y - min_y >= width)
8217 detail::place_inside_box(poly, min_coord, max_coord);
8218 detail::randomize_cyclic_shift(poly);
8222 throw tgen::detail::error(
8223 "geometry: random_orthogonal_polygon: generation failed");
8229
8230
8231
8232
8238using namespace tgen::detail;
8242inline int hash_string(
const std::string &s,
int base,
int mod) {
8245 h = (h * base + c -
'a' + 1) % mod;
8246 return static_cast<
int>(h);
8250inline int estimate_length(
int alphabet_size,
int mod) {
8252 double base_len = 2.5 * std::log(std::sqrt(mod));
8253 double scale = std::log(alphabet_size) / std::log(2.0);
8254 double adjusted = base_len / std::max(1.0, scale * 0.7);
8260 for (
long long ways = 1; ways <= mod; ways *= alphabet_size)
8262 return std::max(min_length,
static_cast<
int>(std::ceil(adjusted)));
8267inline std::pair<std::string, std::string>
8268birthday_attack(
const std::vector<std::string> &alphabet,
int base,
int mod) {
8270 "birthday_attack: base must be in (0, mod)");
8271 std::map<uint64_t, std::vector<
int>> seen;
8272 int length = estimate_length(
static_cast<
int>(alphabet.size()), mod);
8275 std::vector<
int> seq(length);
8279 for (
int i = 0; i < length; ++i) {
8280 seq[i] = next<
int>(0,
static_cast<
int>(alphabet.size()) - 1);
8281 s += alphabet[seq[i]];
8284 int h = hash_string(s, base, mod);
8286 auto it = seen.find(h);
8287 if (it != seen.end()
and it->second != seq) {
8290 for (
int x : it->second)
8305inline std::set<
long long> std_hash_multipliers() {
8306 std::set<
long long> multipliers = {85229};
8309 bool codeforces_gcc_case =
true;
8310 if (cpp.version_ != 0
and cpp.version_ != 17)
8311 codeforces_gcc_case =
false;
8312 if (compiler.kind_ != compiler_kind::unknown
and
8313 compiler.kind_ != compiler_kind::gcc)
8314 codeforces_gcc_case =
false;
8315 if (compiler.major_ > 7)
8316 codeforces_gcc_case =
false;
8318 if (codeforces_gcc_case)
8319 multipliers.insert(107897);
8330 std::string str =
"a";
8332 while (
static_cast<
int>(str.size()) < n) {
8333 int prev_size =
static_cast<
int>(str.size());
8335 for (
int j = 0; j < prev_size
and static_cast<
int>(str.size()) < n; ++j)
8348 for (
int i = 0; i < size; ++i) {
8349 a +=
static_cast<
char>(
'a' + math::detail::popcount(i) % 2);
8350 b +=
static_cast<
char>(
'a' + (
'b' - a[i]));
8359 int base,
int mod) {
8361 "hack: polynomial_hash: alphabet size must be greater "
8364 "hack: polynomial_hash: base must be in (0, mod)");
8366 std::vector<std::string> alphabet(alphabet_size);
8367 for (
int i = 0; i < alphabet_size; ++i)
8368 alphabet[i] = std::string(1,
static_cast<
char>(
'a' + i));
8369 std::iota(alphabet.begin(), alphabet.end(),
'a');
8370 return detail::birthday_attack(alphabet, base, mod);
8377inline std::pair<std::string, std::string>
8379 std::vector<
int> mods) {
8381 "hack: polynomial_hash: alphabet size must be greater "
8384 "hack: polynomial_hash: bases and mods must have the same "
8387 "hack: polynomial_hash: must have at least one (base, mod) "
8390 "hack: polynomial_hash: multi-hash hack only supported "
8391 "for up to 2 (base, mod) pairs");
8393 std::vector<std::string> alphabet(alphabet_size);
8394 for (
int i = 0; i < alphabet_size; ++i)
8395 alphabet[i] = std::string(1,
static_cast<
char>(
'a' + i));
8396 auto [S1, T1] = detail::birthday_attack(alphabet, bases[0], mods[0]);
8397 if (bases.size() == 1)
8399 return detail::birthday_attack({S1, T1}, bases[1], mods[1]);
8405 tgen_ensure(size > 0,
"hack: std_unordered: size must be positive");
8406 std::set<
long long> multipliers = detail::std_hash_multipliers();
8408 std::set<
long long>::iterator it = multipliers.begin();
8410 std::vector<
long long> list;
8411 while (
static_cast<
int>(list.size()) < size) {
8412 list.push_back(mult * (*it));
8414 if (it == multipliers.end()) {
8415 it = multipliers.begin();
8427 std::set<std::pair<
int,
int>> queries;
8430 int sq =
static_cast<
int>(std::sqrt(n));
8431 for (
int i = 0; i < sq; ++i) {
8432 for (
int j = i; j < sq; ++j) {
8433 if (i * sq < n
and j * sq < n)
8434 queries.emplace(i * sq, j * sq);
8439 for (
int i = 0; i < n; ++i)
8440 if (queries.size() < size_t(q)) {
8441 queries.emplace(0, i);
8442 queries.emplace(i, i);
8443 queries.emplace(i, n - 1);
8446 std::vector<std::pair<
int,
int>> pool(queries.begin(), queries.end());
8447 while (pool.size() < size_t(q)) {
8448 int l = next(0, n - 1);
8449 pool.emplace_back(l, next(l, n - 1));
8452 return choose(shuffled(pool), q);
8460 std::vector<std::string> list;
8461 int k = 0, left = size;
8463 int cur_size = std::min(left, k + 1);
8466 char right_char = cur_size == k + 1 ?
'b' :
'c';
8467 list.push_back(std::string(cur_size - 1,
'a') + right_char);
8471 return tgen::shuffled(list);
8483 "hack: non_strict_relaxation_dijkstra_bug: needs at least 3 vertices");
8485 egraph<
int>::value g(n, {},
true);
8487 g.add_edge(0, 1, 1);
8488 g.add_edge(0, 2, 1);
8489 for (
int i = 1; i + 2 < n; i += 2) {
8490 g.add_edge(i, i + 2, 1);
8492 g.add_edge(i, i + 3, 1);
8494 g.add_edge(i + 1, i + 2, 1);
8496 g.add_edge(i + 1, i + 3, 1);
8499 return g.shuffle_except({0});
8512 "hack: stale_heap_dijkstra_bug: needs at least 4 vertices");
8515 egraph<
int>::value g(n, {},
true);
8517 for (
int i = 1; i < mid; ++i)
8518 g.add_edge(0, i, i);
8519 for (
int i = 1; i < mid; ++i)
8520 g.add_edge(i, mid, 2 * (mid - i) - 1);
8521 for (
int i = mid + 1; i < n; ++i)
8522 g.add_edge(mid, i, 1);
8524 return g.shuffle_except({0});
8533 tgen_ensure(n >= 2,
"hack: spfa: n must be at least 2");
8534 tgen_ensure(n % 2 == 0,
"hack: spfa: n must be even");
8535 egraph<
int>::value g(n, {},
true);
8537 const int k = n / 2;
8538 for (
int i = 0; i + 1 < k; ++i) {
8539 g.add_edge(i, i + 1, 1);
8540 g.add_edge(k + i, k + i + 1, 0);
8542 for (
int i = 0; i < k; ++i)
8543 g.add_edge(i, k, 2 * (k - i));
8544 return g.shuffle_except({0});
8552 tgen_ensure(k >= 1,
"hack: dinitz_worst_case: k must be at least 1");
8553 tgen_ensure(l >= 1,
"hack: dinitz_worst_case: l must be at least 1");
8556 const detail::i128 capacity = detail::i128(k) * k * l;
8557 const long long vertices = 4LL * l + 2LL * k + 2;
8558 const long long edges = 6LL * l + 4LL * k + 1LL * k * k - 4;
8559 tgen_ensure(capacity <= std::numeric_limits<
int>::max()
and
8560 vertices <= std::numeric_limits<
int>::max()
and
8561 edges <= std::numeric_limits<
int>::max(),
8562 "hack: dinitz_worst_case: size or capacity too large");
8564 const int p1 = 2 * l - 1;
8565 const int p2 = 2 * l;
8566 const int q1 = 2 * l + 1;
8567 const int q2 = 2 * l + 2;
8568 const int n = 4 * l + 2 * k + 2;
8570 const int flow_cap = k * k * l;
8571 const int layer_cap = k * k;
8573 auto a = [&](
int i) {
return 2 * l + 3 + 2 * i; };
8574 auto b = [&](
int i) {
return 2 * l + 4 + 2 * i; };
8575 auto t = [&](
int i) {
return 4 * l + 2 * k + 1 - i; };
8577 egraph<
int>::value g(n, {},
true);
8580 for (
int i = 0; i + 1 < 2 * l - 1; ++i)
8581 g.add_edge(i, i + 1, flow_cap);
8582 for (
int i = 0; i + 1 < 2 * l - 1; ++i)
8583 g.add_edge(t(i + 1), t(i), flow_cap);
8585 for (
int i = 0; i < 2 * l - 1; i += 2) {
8586 g.add_edge(i, i % 4 == 0 ? p1 : p2, layer_cap);
8587 g.add_edge(i % 4 == 0 ? q1 : q2, t(i), layer_cap);
8590 for (
int i = 0; i < k; ++i) {
8591 g.add_edge(p1, a(i), flow_cap);
8592 g.add_edge(p2, b(i), flow_cap);
8593 g.add_edge(a(i), q2, flow_cap);
8594 g.add_edge(b(i), q1, flow_cap);
8597 for (
int i = 0; i < k; ++i)
8598 for (
int j = 0; j < k; ++j)
8599 g.add_edge(a(i), b(j), 1);
8608 static_assert(std::is_same_v<T,
int>
or std::is_same_v<T,
long long>,
8609 "hack: mt19937_xor_hash: T must be int or long long");
8611 constexpr std::size_t deg = 19937;
8613 std::bitset<deg + 1> a, b, c;
8614 b[deg] = c[deg] = 1;
8615 std::size_t l = 0, shift = 1;
8617 std::mt19937_64 rng64;
8618 for (std::size_t n = 0; n < deg * 2; ++n) {
8620 if constexpr (std::is_same_v<T,
int>)
8621 a[deg] = rng32() & 1;
8623 a[deg] = rng64() & 1;
8625 if ((c & a).count() % 2 == 0) {
8630 std::bitset<deg + 1> oc = c;
8641 std::vector<
bool> mask(deg + 1);
8642 for (std::size_t i = 0; i <= deg; ++i)
8654 {-0.9846, -1.53251}, {0.49946, 1.19525}, {0.79916, 0.98291},
8655 {4.02136, -1.57843}, {3.92734, -2.37856}, {3.88558, -2.37188},
8663inline std::vector<
int> segment_tree_beats_worst_case_block(
int k) {
8665 "hack: segment_tree_beats_worst_case: k must be at least 1");
8667 std::vector<
int> a(k + 1), b(k + 1);
8668 std::vector<std::vector<
int>> vf(k + 1), vg(k + 1);
8674 for (
int i = 2; i <= k; ++i) {
8675 b[i] = b[i - 1] + a[i - 1];
8676 a[i] = b[i] + a[i - 1];
8677 for (
int x : vf[i - 1])
8678 vf[i].push_back(x + a[i] + b[i]);
8679 vf[i].push_back(a[i]);
8680 for (
int x : vg[i - 1])
8681 vf[i].push_back(x + a[i]);
8684 for (
int x : vg[i - 1])
8695segment_tree_beats_append_round(std::vector<std::vector<
int>> &updates,
8696 int block_len,
int an,
int bn,
int n,
8698 const int off = (round * an) % block_len;
8699 const int add_off = (off + block_len - bn) % block_len;
8700 for (
int k = 0; k < block_len; ++k) {
8701 const int s = k * block_len * block_len;
8702 const int sub_end = off + an;
8703 if (sub_end <= block_len)
8704 updates.push_back({1, s + off, s + sub_end, bn});
8706 updates.push_back({1, s + off, s + block_len, bn});
8707 updates.push_back({1, s, s + (sub_end - block_len), bn});
8709 const int add_end = add_off + bn;
8710 if (add_end <= block_len)
8711 updates.push_back({0, s + add_off, s + add_end, an});
8713 updates.push_back({0, s + add_off, s + block_len, an});
8714 updates.push_back({0, s, s + (add_end - block_len), an});
8717 updates.push_back({2, 0, n, an});
8718 for (
int k = 0; k < block_len; ++k) {
8719 const int s = k * block_len * block_len;
8720 updates.push_back({3, s + (off + an - 1) % block_len, 0});
8728inline std::pair<std::vector<
int>, std::vector<std::vector<
int>>>
8729segment_tree_beats_worst_case(
int k,
int q) {
8731 "hack: segment_tree_beats_worst_case: k must be at least 1");
8732 tgen_ensure(k <= 7,
"hack: segment_tree_beats_worst_case: k too large");
8734 "hack: segment_tree_beats_worst_case: q must be positive");
8736 const auto &fib = math::fibonacci();
8737 const int block_len =
static_cast<
int>(fib[k * 2 + 1]);
8738 const int an =
static_cast<
int>(fib[k * 2]);
8739 const int bn =
static_cast<
int>(fib[k * 2 - 1]);
8741 const int len = block_len;
8742 const int total = len * len * len;
8744 std::vector<
int> block = detail::segment_tree_beats_worst_case_block(k);
8745 std::vector<
int> arr(total, 0);
8746 for (
int x = 0; x < block_len; ++x) {
8747 const int s = x * len * len;
8748 for (
int i = 0; i < block_len; ++i)
8749 arr[s + i] = block[i];
8752 std::vector<std::vector<
int>> updates;
8754 const int n = total;
8755 for (
int round = 0; updates.size() <
static_cast<std::size_t>(q); ++round) {
8756 detail::segment_tree_beats_append_round(updates, block_len, an, bn, n,
8758 if (updates.size() >
static_cast<std::size_t>(q))
8761 return {arr, updates};
8769inline tree::value binary_heap_tree(
int n) {
8770 std::vector<std::pair<
int,
int>> edges;
8771 for (
int i = 0; i < n; ++i) {
8773 edges.emplace_back(i, 2 * i + 1);
8775 edges.emplace_back(i, 2 * i + 2);
8777 return tree::value(n, edges);
8782inline void heap_subtree_leaves(
int n,
int u, std::vector<
int> &out) {
8783 if (2 * u + 1 >= n) {
8787 heap_subtree_leaves(n, 2 * u + 1, out);
8789 heap_subtree_leaves(n, 2 * u + 2, out);
8796inline std::vector<std::pair<
int,
int>> tree_path_worst_queries(
int n,
int q) {
8797 std::vector<
int> left, right;
8799 heap_subtree_leaves(n, 1, left);
8801 heap_subtree_leaves(n, 2, right);
8803 std::vector<std::pair<
int,
int>> queries;
8804 for (
int i = 0; i < q; ++i)
8805 queries.emplace_back(pick(left), pick(right));
8811inline int reverse_bits(
int x,
int bits) {
8813 for (
int i = 0; i < bits; ++i) {
8814 r = (r << 1) | (x & 1);
8824inline std::vector<
int> lct_worst_access(
int n,
int q) {
8825 int first_leaf = n / 2;
8826 int m = n - first_leaf;
8829 while ((1u << bits) <
static_cast<
unsigned>(m))
8832 std::vector<
int> order;
8833 int span = 1 << bits;
8834 for (
int i = 0; i < span; ++i) {
8835 int r = reverse_bits(i, bits);
8837 order.push_back(first_leaf + r);
8840 std::vector<
int> access;
8841 for (
int i = 0; i < q; ++i)
8842 access.push_back(order[i % m]);
8851inline std::pair<tree::value, std::vector<std::pair<
int,
int>>>
8852centroid_decomposition_worst_case(
int n,
int q) {
8855 "hack: centroid_decomposition_worst_case: n must be at least 3");
8858 "hack: centroid_decomposition_worst_case: q must be at least 1");
8860 return {detail::binary_heap_tree(n), detail::tree_path_worst_queries(n, q)};
8866inline std::pair<tree::value, std::vector<std::pair<
int,
int>>>
8867heavy_light_decomposition_worst_case(
int n,
int q) {
8870 "hack: heavy_light_decomposition_worst_case: n must be at least "
8874 "hack: heavy_light_decomposition_worst_case: q must be at least 1");
8876 return {detail::binary_heap_tree(n), detail::tree_path_worst_queries(n, q)};
8881inline std::pair<tree::value, std::vector<
int>>
8882link_cut_tree_worst_case(
int n,
int q) {
8883 tgen_ensure(n >= 2,
"hack: link_cut_tree_worst_case: n must be at least 2");
8884 tgen_ensure(q >= 1,
"hack: link_cut_tree_worst_case: q must be at least 1");
8886 return {detail::binary_heap_tree(n), detail::lct_worst_access(n, q)};
8892
8893
8894
8895
8904 "misc: parenthesis: size must be a positive even number");
8908 int open = 0, close = 0;
8910 for (
int i = 0; i < size; ++i) {
8916 if (open == close) {
8922 long long a = k - open, b = k - close, h = open - close;
8927 long long num = a * (h + 2);
8928 long long den = (a + b) * (h + 1);
8930 if (next<
long long>(1, den) <= num) {
std::vector< int > many_by_distribution(int k, const std::vector< T > &distribution)
Returns many random indices with given probabilities.
auto shuffled(const C &container)
Shuffles a container.
C::value_type pick(const C &container)
Chooses a random element from container.
void shuffle(It first, It last)
Shuffles range inplace, for random_access_iterator.
T wnext(T left, T right, int w)
Returns a skewed random number in range.
It::value_type pick(It first, It last)
Chooses a random element from an iterator range.
T next(T right)
Returns a random number smaller than value.
size_t next_by_distribution(const std::vector< T > &distribution)
Returns random index with given probabilities.
C::value_type pick_by_distribution(const C &container, std::vector< T > distribution)
Chooses a random element with given probabilities.
#define tgen_ensure(cond,...)
Ensures condition is true.
T next(T left, T right)
Returns a random number in range.
T wnext(T right, int w)
Returns a skewed random number smaller than value.
C choose(const C &container, int k)
Chooses elements from container, as in a subsequence fixed length.
std::vector< point< long long > > random_simple_polygon_through_points(const std::vector< point< long long > > &points)
Generates a random simple polygon through given points.
std::vector< point< long long > > random_points_general_position(int n, long long min_coord, long long max_coord)
Generates random points in general position inside a coordinate box.
std::vector< point< long long > > random_convex_polygon(int n, long long min_coord, long long max_coord, bool strict=false)
Generates a random convex polygon with given coordinate range.
std::vector< point< long long > > random_simple_polygon(int n, long long min_coord, long long max_coord, bool strict=false)
Generates a random simple polygon given coordinate range.
std::vector< point< long long > > random_orthogonal_polygon(int n, long long min_coord, long long max_coord, bool strict=false)
Generates a random orthogonal simple polygon.
wgraph< VWeight, int > vgraph
Vertex-weighted labeled graphs.
graph::value C(int n, bool is_directed=false)
Cycle graph.
wgraph< int, EWeight > egraph
Edge-weighted labeled graphs.
graph::value S(int n)
Star undirected graph.
graph::value K(int n1, int n2)
Complete bipartite undirected graph.
graph::value K(int n)
Complete undirected graph.
wgraph< int, int > graph
Unweighted labeled graphs.
graph::value P(int n, bool is_directed=false)
Path graph.
std::vector< std::pair< int, int > > mo_worst_case(int n, int q)
Query list that forces asymptotic worst-case for Mo's algorithm.
std::vector< bool > mt19937_xor_hash()
Mask that forces a zero XOR hash from std::mt19937 or std::mt19937_64.
egraph< int >::value spfa(int n)
Worst-case for FIFO-SPFA.
egraph< int >::value non_strict_relaxation_dijkstra_bug(int n)
Directed weighted graph for Dijkstra with non-strict relaxation.
std::string abacaba(int n)
Returns the prefix of the infinite word "abacabad...".
std::vector< geometry::point< double > > naive_rotating_calipers_max_dist_bug()
Convex polygon that breaks naive rotating calipers for maximum distance.
std::vector< long long > std_unordered(int size)
List of integers that tries to force collision on std::unordered_set.
std::vector< std::string > string_set_worst_case(int size)
List of strings that have high cost to insert in a std::set.
std::pair< std::string, std::string > unsigned_polynomial_hash()
Returns two strings that force polynomial hash collision for power-of-two mod.
std::pair< std::string, std::string > polynomial_hash(int alphabet_size, int base, int mod)
Returns two strings that force polynomial hash collision given base and mod.
egraph< int >::value dinitz_worst_case(int k, int l)
Flow network for Edmonds-Karp and Dinitz worst-case.
egraph< int >::value stale_heap_dijkstra_bug(int n)
Directed weighted graph for Dijkstra without a stale-heap check.
uint64_t prime_from(uint64_t left)
Computes smallest prime from given value.
uint64_t gen_divisor_count(uint64_t left, uint64_t right, int divisor_count)
Generates random number in range with a given prime number of divisors.
std::vector< int > gen_partition_fixed_size(int n, int k, int part_left=0, std::optional< int > part_right=std::nullopt)
Generates a random partition with fixed size of a number.
uint64_t totient(uint64_t n)
Euler's totient function.
uint64_t congruent_from(uint64_t left, std::vector< uint64_t > rems, std::vector< uint64_t > mods)
Computes smallest congruent from given value.
uint64_t congruent_upto(uint64_t right, uint64_t rem, uint64_t mod)
Computes largest congruent up to given value.
uint64_t gen_prime(uint64_t left, uint64_t right)
Generates a random prime in given range.
std::vector< uint64_t > factor(uint64_t n)
Factors a number into primes.
int num_divisors(uint64_t n)
Computes the number of divisors of a given number.
bool is_prime(uint64_t n)
Checks if a number is prime.
std::vector< int > gen_partition(int n, int part_left=1, std::optional< int > part_right=std::nullopt)
Generates a random partition of a number.
constexpr int FFT_MOD
FFT/NTT mod.
uint64_t gen_congruent(uint64_t left, uint64_t right, uint64_t rem, uint64_t mod)
Generates random number in range given a modular congruence.
uint64_t prime_upto(uint64_t right)
Computes largest prime up to given value.
uint64_t highly_composite_upto(uint64_t right)
Largest highly composite number up to given number.
uint64_t congruent_upto(uint64_t right, std::vector< uint64_t > rems, std::vector< uint64_t > mods)
Computes largest congruent up to given value.
std::vector< std::pair< uint64_t, int > > factor_by_prime(uint64_t n)
Factors a number into primes and its powers.
const std::vector< uint64_t > & fibonacci()
Fetches Fibonacci numbers.
uint64_t modular_inverse(uint64_t a, uint64_t mod)
Computes modular inverse.
uint64_t congruent_from(uint64_t left, uint64_t rem, uint64_t mod)
Computes smallest congruent from given value.
const std::vector< uint64_t > & highly_composites()
Fetches highly composite numbers.
std::vector< std::vector< T > > partition_elements(std::vector< T > elements, int k, int min_size=0, std::optional< uint64_t > max_size=std::nullopt)
Partitions a vector into k ordered groups.
std::vector< uint64_t > gen_partition_fixed_size_fast(uint64_t n, int k, uint64_t part_left=0, std::optional< uint64_t > part_right=std::nullopt)
Generates a fast non-uniform partition with fixed size.
uint64_t gen_congruent(uint64_t left, uint64_t right, std::vector< uint64_t > rems, std::vector< uint64_t > mods)
Generates random number in range given modular congruences.
std::pair< uint64_t, uint64_t > prime_gap_upto(uint64_t right)
Largest prime gap up to given number.
std::string gen_parenthesis(int size)
Generates a random valid parenthesis sequence.
T opt(const std::string &key, std::optional< T > default_value=std::nullopt)
Gets opt by key.
void set_compiler(compiler_value compiler)
Sets compiler.
T opt(size_t index, std::optional< T > default_value=std::nullopt)
Gets opt by key.
bool has_opt(std::size_t index)
Checks if opt at some index exists.
bool has_opt(const std::string &key)
Checks if opt with some key exists.
void set_cpp_version(int version)
Sets C++ version.
void register_gen(std::optional< long long > seed=std::nullopt)
Sets up the generator without arguments.
void register_gen(int argc, char **argv)
Sets up the generator.
wtree< VWeight, int > vtree
Vertex-weighted labeled trees.
wtree< int, EWeight > etree
Edge-weighted labeled trees.
wtree< int, int > tree
Unweighted labeled trees.
Compiler identity and version.
Distinct generator for containers.
auto gen_list(int size)
Generates a list of several distinct elements.
T gen()
Generates a distinct random element from the container.
distinct_container(const C &container)
Creates distinct generator for elements of the given container.
auto gen_all()
Generates all distinct elements left to generate.
size_t size() const
Returns the number of elements left to generate.
Distinct generator for integral ranges.
auto gen_list(int count)
Generates a list of several distinct values.
distinct_range(T left, T right)
Creates distinct generator for values in given range.
auto gen_all()
Generates all distinct values left to generate.
T gen()
Generates a distinct random value in the defined range.
count_type size() const
Returns the number of values left to generate.
Distinct generator for discrete uniform functions.
distinct(Func func, Args... args)
Generates a distinct generator of a discrete uniform function.
auto gen_list(int size)
Generates a list of several distinct values.
bool empty()
Checks if there is nothing left to generate.
auto gen_all()
Generates all distinct values left to generate.
auto gen()
Generates a distinct value.
Base class for generators (should not be instantiated).
auto gen_list(int size, Args &&...args) const
Generates a list of several generation calls.
auto gen_until(Pred predicate, int max_tries, Args &&...args) const
Generates a random value from the valid set until a condition is met.
auto distinct(Args &&...args) const
Creates distinct generator for current generator.
Base class for generator values (should not be instantiated).
bool operator<(const Val &rhs) const
bool operator==(const point &p) const
Coordinate-wise equality.
product_t operator*(const point &p) const
Dot product.
product_t operator^(const point &p) const
Cross product.
point operator*(T c) const
Scalar multiplication.
point operator-(const point &p) const
Vector subtraction.
point(T x=0, T y=0)
Constructs a point.
bool operator<(const point &p) const
Lexicographic order.
point operator+(const point &p) const
Vector addition.
int size() const
Returns the size of the list value.
value(const std::vector< T > &vec)
Creates a list value from a std::vector.
value & sort()
Sorts the list in non-decreasing order.
auto to_std() const
Converts the list to a std::vector.
value & separator(char sep)
Sets separator for printing.
value choose(int k) const
Chooses a uniformly random subsequence of given length.
value operator+(const value &rhs) const
Concatenates two lists.
T & operator[](int idx)
Accesses the element at some position of the list.
value & reverse()
Reverses the list.
T pick_by_distribution(const std::vector< Dist > &distribution) const
Returns a random element from the list with given probabilities.
value & shuffle()
Shuffles the list in place.
T pick() const
Returns a uniformly random element.
list & different(int idx_1, int idx_2)
Restricts generator s.t. values at two indices are different.
list & equal(int idx_1, int idx_2)
Restricts generator s.t. values at two indices are equal.
list & adjacent_different()
Restricts generator s.t. adjacent values are different.
list & all_different()
Restricts generator s.t. all values are different.
list & equal_range(int left, int right)
Restricts generator s.t. all values at index range are equal.
list(int size, std::set< T > values)
Creates list generator defined by value set.
value gen() const
Generates a uniformly random value from the set of valid lists.
list & all_equal()
Restricts generator s.t. all values are equal.
list & different(std::set< int > indices)
Restricts generator s.t. all values in index set are different.
list & different_range(int left, int right)
Restricts generator s.t. all values at index range are different.
list(int size, T value_left, T value_right)
Creates list generator defined by size and range of values.
list & fix(int idx, T val)
Restricts generator s.t. value at index is fixed.
list & equal(std::set< int > indices)
Restricts generator s.t. all values in index set are equal.
T second() const
Returns the second element of a pair value.
value(const T &first, const T &second)
Creates a pair value from first and second values.
value(const std::pair< T, T > &pair)
Creates a pair value from a std::pair.
auto to_std() const
Converts the pair to a std::pair.
T first() const
Returns the first element of a pair value.
value & separator(char sep)
Sets separator for printing.
value gen() const
Generates a uniformly random value from the set of valid pairs.
pair & neq()
Restricts generator s.t. first is not equal to second.
pair & leq()
Restricts generator s.t. first is less than or equal to second.
pair & lt()
Restricts generator s.t. first is less than second.
pair & gt()
Restricts generator s.t. first is greater than second.
pair(T both_left, T both_right)
Creates pair generator defined by range of values for both first and second.
pair & eq()
Restricts generator s.t. first is equal to second.
pair(T first_left, T first_right, T second_left, T second_right)
Creates pair generator defined by range of values for first and second.
pair & geq()
Restricts generator s.t. first is greater than or equal to second.
value & print_1_based()
Sets that printed values are 1-based.
std::vector< int > to_std() const
Converts the permutation to a std::vector.
const int & operator[](int idx) const
Returns the image at some position of the permutation.
std::vector< int > to_std_1_based() const
Converts the permutation to a 1-based std::vector.
value & sort()
Sorts the permutation in non-decreasing order.
int parity() const
Parity of the permutation.
int pick_by_distribution(const std::vector< Dist > &distribution) const
Returns a random element from the permutation with given probabilities.
int pick() const
Returns a uniformly random element.
value & reverse()
Reverses the permutation.
value(const std::vector< int > &vec)
Creates a permutation value from a std::vector.
int size() const
Returns the size of the permutation value.
value & shuffle()
Shuffles the permutation.
value & inverse()
Inverse of the permutation.
value & separator(char sep)
Sets separator for printing.
value gen() const
Generates a uniformly random value from the set of valid permutations.
permutation & cycles(const std::vector< int > &cycle_sizes)
Restricts generator s.t. cycle sizes are fixed.
permutation(int size)
Creates permutation generator defined by size.
permutation & fix(int idx, int val)
Restricts generator s.t. value at index is fixed.
Printer helper for printing containers or sequential generator elements as columns.
print_cols(const Args &...args)
Creates a printer object that prints as columns.
Printer helper for standard types.
print(const T &val, char sep=' ')
Creates a printer object.
Printer helper for standard types, printing on a new line.
println(const T &val, char sep=' ')
Creates a printer object that prints on a new line.
char pick() const
Returns a uniformly random element.
char pick_by_distribution(const std::vector< Dist > &distribution) const
Returns a random element from the string with given probabilities.
value choose(int k) const
Chooses a uniformly random subsequence of given length.
value & lowercase()
Sets all characters to lowercase.
value & reverse()
Reverses the string.
int size() const
Returns the size of the string value.
value(const std::string &str)
Creates a string value from a std::string.
value & shuffle()
Shuffles the string.
char & operator[](int idx)
Accesses the character at some position of the string.
value & uppercase()
Sets all characters to uppercase.
value operator+(const value &rhs) const
Concatenates two strings.
std::string to_std() const
Converts the string to a std::string.
value & sort()
Sorts the characters in non-decreasing order.
str & different(int idx_1, int idx_2)
Restricts generator s.t. characters at two indices are different.
str & palindrome(int left, int right)
Restricts generator s.t. range is a palindrome.
value gen() const
Generates a uniformly random value from the set of valid strings.
str(int size, char value_left='a', char value_right='z')
Creates string generator defined by size and range of characters.
str & different(std::set< int > indices)
Restricts generator s.t. all characters in index set are different.
str(const std::string ®ex, Args &&...args)
Creates string generator defined by regex.
str & equal(int idx_1, int idx_2)
Restricts generator s.t. characters at two indices are equal.
str & equal(std::set< int > indices)
Restricts generator s.t. all characters in index set are equal.
str & equal_range(int left, int right)
Restricts generator s.t. all characters at index range are equal.
str & fix(int idx, char character)
Restricts generator s.t. character at index is fixed.
str & all_equal()
Restricts generator s.t. all values are equal.
str & different_range(int left, int right)
Restricts generator s.t. all characters at index range are different.
str & palindrome()
Restricts generator s.t. string is a palindrome.
str & all_different()
Restricts generator s.t. all characters are different.
str(int size, std::set< char > chars)
Creates string generator defined by character set.
str & adjacent_different()
Restricts generator s.t. adjacent values are different.
Sampler for repeated draws from a fixed weighted distribution.
size_t next() const
Generates a random index with probability proportional to the distribution.
weighted_sampler(const std::vector< T > &distribution)
Creates a weighted sampler from a probability distribution.
value & print_nm()
Prints number of vertices and edges before edge list.
const std::optional< std::vector< VWeight > > & vertex_weights() const
Optional vertex weights.
value operator!() const
Graph complement of unweighted graph.
std::tuple< int, int, std::vector< std::set< int > > > to_std() const
Converts the graph to std types.
value & shuffle_except(std::set< int > indices)
Shuffles vertices except given vertices, and edge order.
int n() const
Number of vertices.
value operator+(const value &rhs) const
Concatenates two graphs (disjoint union).
value & disjoint_union(const value &rhs)
Disjoint union with another graph.
int m() const
Number of edges.
std::tuple< int, int, std::vector< std::set< int > > > to_std_1_based() const
Converts the graph to 1-based std types.
value & glue(const value &rhs, std::set< std::pair< int, int > > index_pairs)
Glues another graph at given vertex pairs.
const std::optional< std::vector< EWeight > > & edge_weights() const
Optional edge weights.
value(const std::vector< std::set< int > > &adj, bool is_directed=false)
Builds a graph from an adjacency list.
value(int n, const std::vector< std::pair< int, int > > &edges={}, bool is_directed=false)
Builds a graph from number of vertices and edge list.
wgraph< NewVWeight, EWeight >::value set_vertex_weights(const std::vector< NewVWeight > &vertex_weights) const
Attaches vertex weights.
const std::vector< std::set< int > > & adj() const
Adjacency list.
value & add_vertices(int k, std::optional< std::vector< VWeight > > new_vertex_weights=std::nullopt)
Adds new isolated vertices.
value & print_1_based()
Sets that printed vertex ids are 1-based.
value & random_connected_subgraph(int num_edges)
Random subgraph with a fixed number of edges that keeps components connected.
value(const typename wtree< VWeight, EWeight >::value &t)
Builds an undirected graph from a tree.
value & random_subgraph(int num_edges)
Random subgraph with a fixed number of edges.
value & edge_weighted()
Enables edge-weighted mode on an edgeless graph.
value & link(const value &rhs, int new_u, int new_v, std::optional< EWeight > new_w=std::nullopt)
Links two graphs by an new edge.
bool is_directed() const
If the graph is directed.
value & add_edge(int u, int v, std::optional< EWeight > w=std::nullopt)
Adds an edge between two vertices.
value & shuffle()
Shuffles all vertices and edge order.
wgraph< VWeight, NewEWeight >::value set_edge_weights(const std::vector< NewEWeight > &edge_weights) const
Attaches edge weights.
const std::vector< std::pair< int, int > > & edges() const
Edge list.
Labeled weighted graph generator.
wgraph(int n, int m, bool is_directed=false, bool has_self_loops=false)
Creates a graph generator for a fixed number of vertices and edges.
static value gen_bipartite(int n1, int n2, int m, bool connected=false)
Generates a random bipartite graph.
value get_connected() const
Random connected undirected graph extending preset edges.
static value gen_np(int n, double p, bool is_directed=false, bool has_self_loops=false)
Generates a random graph where each edge is included independently.
value gen() const
Generates a uniformly random graph satisfying the constraints.
wgraph & add_edge(int u, int v)
Adds a preset edge that must appear in the generated graph.
value get_acyclic() const
Random directed acyclic graph extending preset edges.
static value gen_skewed(int n, int m, int elongation, int spread, bool is_directed=false)
Random skewed connected graph (large diameter).
wgraph & add_edges_from(const value &rhs)
Adds all edges from another graph as preset edges.
value & glue(const value &rhs, std::set< std::pair< int, int > > index_pairs)
Glues another tree at given vertex pairs.
const std::vector< std::pair< int, int > > & edges() const
Edge list.
value(int n, const std::vector< std::pair< int, int > > &edges)
Builds a tree from a vertex count and an edge list.
value(const typename wgraph< VWeight, EWeight >::value &g)
Builds a tree from a graph via a Kruskal-like random spanning tree.
value & print_parents(int root=-1)
Prints in parent format instead of edge list.
const std::optional< std::vector< VWeight > > & vertex_weights() const
Optional vertex weights.
value & edge_weighted()
Enables edge-weighted mode on an edgeless tree.
int n() const
Returns the number of vertices.
value & shuffle_except(std::set< int > indices)
Shuffles vertices except given vertices, and edge order.
const std::vector< std::set< int > > & adj() const
Adjacency list.
value(const std::vector< std::set< int > > &adj)
Builds a tree from an adjacency list.
const std::optional< std::vector< EWeight > > & edge_weights() const
Optional edge weights.
value & shuffle()
Shuffles vertices and edge order.
std::pair< int, std::vector< std::set< int > > > to_std() const
Converts the tree to a std types.
wtree< NewVWeight, EWeight >::value set_vertex_weights(const std::vector< NewVWeight > &vertex_weights) const
Attaches vertex weights.
value & print_n()
Prints the number of vertices before the tree.
std::pair< int, std::vector< std::set< int > > > to_std_1_based() const
Converts the tree to 1-based std types.
value & link(const value &rhs, int new_u, int new_v, std::optional< EWeight > new_w=std::nullopt)
Links two trees by an edge.
value & print_1_based()
Sets that printed vertex ids are 1-based.
wtree< VWeight, NewEWeight >::value set_edge_weights(const std::vector< NewEWeight > &edge_weights) const
Attaches edge weights.
Labeled weighted tree generator.
wtree & add_edge(int u, int v)
Restricts generator s.t. some edge is present.
static value gen_skewed(int n, int elongation)
Random skewed tree (large diameter).
value gen() const
Generates a uniformly random value from the set of valid trees.
wtree(int n)
Creates a tree generator with specified number of vertices.
static value gen_kruskal(int n)
Kruskal-like random labeled tree.