結果
| 問題 | No.5020 Averaging |
| ユーザー |
 Rafbill
|
| 提出日時 | 2024-02-25 16:59:12 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 908 ms / 1,000 ms |
| コード長 | 32,317 bytes |
| コンパイル時間 | 4,869 ms |
| コンパイル使用メモリ | 385,952 KB |
| 実行使用メモリ | 143,920 KB |
| スコア | 90,206,883 |
| 最終ジャッジ日時 | 2024-02-25 17:02:54 |
| 合計ジャッジ時間 | 50,861 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 839 ms
143,868 KB |
| testcase_01 | AC | 869 ms
143,868 KB |
| testcase_02 | AC | 844 ms
143,920 KB |
| testcase_03 | AC | 898 ms
143,868 KB |
| testcase_04 | AC | 843 ms
143,868 KB |
| testcase_05 | AC | 887 ms
143,868 KB |
| testcase_06 | AC | 875 ms
143,868 KB |
| testcase_07 | AC | 863 ms
143,868 KB |
| testcase_08 | AC | 884 ms
143,868 KB |
| testcase_09 | AC | 891 ms
143,868 KB |
| testcase_10 | AC | 880 ms
143,868 KB |
| testcase_11 | AC | 861 ms
143,868 KB |
| testcase_12 | AC | 881 ms
143,868 KB |
| testcase_13 | AC | 835 ms
143,868 KB |
| testcase_14 | AC | 889 ms
143,868 KB |
| testcase_15 | AC | 853 ms
143,868 KB |
| testcase_16 | AC | 868 ms
143,868 KB |
| testcase_17 | AC | 845 ms
143,868 KB |
| testcase_18 | AC | 847 ms
143,868 KB |
| testcase_19 | AC | 844 ms
143,868 KB |
| testcase_20 | AC | 817 ms
143,868 KB |
| testcase_21 | AC | 827 ms
143,868 KB |
| testcase_22 | AC | 875 ms
143,868 KB |
| testcase_23 | AC | 814 ms
143,868 KB |
| testcase_24 | AC | 852 ms
143,868 KB |
| testcase_25 | AC | 888 ms
143,868 KB |
| testcase_26 | AC | 850 ms
143,868 KB |
| testcase_27 | AC | 887 ms
143,868 KB |
| testcase_28 | AC | 905 ms
143,868 KB |
| testcase_29 | AC | 805 ms
143,868 KB |
| testcase_30 | AC | 857 ms
143,868 KB |
| testcase_31 | AC | 812 ms
143,868 KB |
| testcase_32 | AC | 889 ms
143,868 KB |
| testcase_33 | AC | 881 ms
143,868 KB |
| testcase_34 | AC | 811 ms
143,868 KB |
| testcase_35 | AC | 872 ms
143,868 KB |
| testcase_36 | AC | 882 ms
143,868 KB |
| testcase_37 | AC | 796 ms
143,868 KB |
| testcase_38 | AC | 856 ms
143,868 KB |
| testcase_39 | AC | 839 ms
143,868 KB |
| testcase_40 | AC | 833 ms
143,868 KB |
| testcase_41 | AC | 879 ms
143,868 KB |
| testcase_42 | AC | 884 ms
143,868 KB |
| testcase_43 | AC | 801 ms
143,868 KB |
| testcase_44 | AC | 875 ms
143,868 KB |
| testcase_45 | AC | 810 ms
143,868 KB |
| testcase_46 | AC | 833 ms
143,868 KB |
| testcase_47 | AC | 908 ms
143,868 KB |
| testcase_48 | AC | 805 ms
143,868 KB |
| testcase_49 | AC | 847 ms
143,868 KB |
コンパイルメッセージ
main.cpp: In function 'void print_answer(std::vector<std::array<int, 2> >)':
main.cpp:708:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
708 | for(auto [x,y] : ans) {
| ^
ソースコード
#pragma GCC optimize "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math"
#pragma GCC target "tune=native"
#include <bits/stdc++.h>
#include <sys/time.h>
#include <immintrin.h>
#include <x86intrin.h>
using namespace std;
// Macros
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
// Types
template<class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
template<class T>
using max_queue = priority_queue<T>;
// Printing
template<class T>
void print_collection(ostream& out, T const& x);
template<class T, size_t... I>
void print_tuple(ostream& out, T const& a, index_sequence<I...>);
namespace std {
template<class... A>
ostream& operator<<(ostream& out, tuple<A...> const& x) {
print_tuple(out, x, index_sequence_for<A...>{});
return out;
}
template<class... A>
ostream& operator<<(ostream& out, pair<A...> const& x) {
print_tuple(out, x, index_sequence_for<A...>{});
return out;
}
template<class A, size_t N>
ostream& operator<<(ostream& out, array<A, N> const& x) { print_collection(out, x); return out; }
template<class A>
ostream& operator<<(ostream& out, vector<A> const& x) { print_collection(out, x); return out; }
template<class A>
ostream& operator<<(ostream& out, deque<A> const& x) { print_collection(out, x); return out; }
template<class A>
ostream& operator<<(ostream& out, multiset<A> const& x) { print_collection(out, x); return out; }
template<class A, class B>
ostream& operator<<(ostream& out, multimap<A, B> const& x) { print_collection(out, x); return out; }
template<class A>
ostream& operator<<(ostream& out, set<A> const& x) { print_collection(out, x); return out; }
template<class A, class B>
ostream& operator<<(ostream& out, map<A, B> const& x) { print_collection(out, x); return out; }
template<class A, class B>
ostream& operator<<(ostream& out, unordered_set<A> const& x) { print_collection(out, x); return out; }
}
template<class T, size_t... I>
void print_tuple(ostream& out, T const& a, index_sequence<I...>){
using swallow = int[];
out << '(';
(void)swallow{0, (void(out << (I == 0? "" : ", ") << get<I>(a)), 0)...};
out << ')';
}
template<class T>
void print_collection(ostream& out, T const& x) {
int f = 0;
out << '[';
for(auto const& i: x) {
out << (f++ ? "," : "");
out << i;
}
out << "]";
}
// Random
struct RNG {
uint64_t s[2];
RNG(u64 seed) {
reset(seed);
}
RNG() {
reset(time(0));
}
using result_type = u32;
constexpr u32 min(){ return numeric_limits<u32>::min(); }
constexpr u32 max(){ return numeric_limits<u32>::max(); }
u32 operator()() { return randomInt32(); }
static __attribute__((always_inline)) inline uint64_t rotl(const uint64_t x, int k) {
return (x << k) | (x >> (64 - k));
}
inline void reset(u64 seed) {
struct splitmix64_state {
u64 s;
u64 splitmix64() {
u64 result = (s += 0x9E3779B97f4A7C15);
result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;
result = (result ^ (result >> 27)) * 0x94D049BB133111EB;
return result ^ (result >> 31);
}
};
splitmix64_state sm { seed };
s[0] = sm.splitmix64();
s[1] = sm.splitmix64();
}
uint64_t next() {
const uint64_t s0 = s[0];
uint64_t s1 = s[1];
const uint64_t result = rotl(s0 * 5, 7) * 9;
s1 ^= s0;
s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
s[1] = rotl(s1, 37); // c
return result;
}
inline u32 randomInt32() {
return next();
}
inline u64 randomInt64() {
return next();
}
inline u32 random32(u32 r) {
return (((u64)randomInt32())*r)>>32;
}
inline u64 random64(u64 r) {
return randomInt64()%r;
}
inline u32 randomRange32(u32 l, u32 r) {
return l + random32(r-l+1);
}
inline u64 randomRange64(u64 l, u64 r) {
return l + random64(r-l+1);
}
inline double randomDouble() {
return (double)randomInt32() / 4294967296.0;
}
inline float randomFloat() {
return (float)randomInt32() / 4294967296.0;
}
inline double randomRangeDouble(double l, double r) {
return l + randomDouble() * (r-l);
}
template<class T>
void shuffle(vector<T>& v) {
i32 sz = v.size();
for(i32 i = sz; i > 1; i--) {
i32 p = random32(i);
swap(v[i-1],v[p]);
}
}
template<class T>
void shuffle(T* fr, T* to) {
i32 sz = distance(fr,to);
for(int i = sz; i > 1; i--) {
int p = random32(i);
swap(fr[i-1],fr[p]);
}
}
template<class T>
inline int sample_index(vector<T> const& v) {
return random32(v.size());
}
template<class T>
inline T sample(vector<T> const& v) {
return v[sample_index(v)];
}
} rng;
// Letrec
template<class Fun>
class letrec_result {
Fun fun_;
public:
template<class T>
explicit letrec_result(T &&fun): fun_(forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(ref(*this), forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) letrec(Fun &&fun) {
return letrec_result<decay_t<Fun>>(forward<Fun>(fun));
}
// Timer
struct timer {
chrono::high_resolution_clock::time_point t_begin;
timer() {
t_begin = chrono::high_resolution_clock::now();
}
void reset() {
t_begin = chrono::high_resolution_clock::now();
}
float elapsed() const {
return chrono::duration<float>(chrono::high_resolution_clock::now() - t_begin).count();
}
};
// Util
template<class T>
T& smin(T& x, T const& y) { x = min(x,y); return x; }
template<class T>
T& smax(T& x, T const& y) { x = max(x,y); return x; }
template<typename T>
int sgn(T val) {
if(val < 0) return -1;
if(val > 0) return 1;
return 0;
}
static inline
string int_to_string(int val, int digits = 0) {
string s = to_string(val);
reverse(begin(s), end(s));
while((int)s.size() < digits) s.push_back('0');
reverse(begin(s), end(s));
return s;
}
// Debug
static inline void debug_impl_seq() {
cerr << "}";
}
template <class T, class... V>
void debug_impl_seq(T const& t, V const&... v) {
cerr << t;
if(sizeof...(v)) { cerr << ", "; }
debug_impl_seq(v...);
}
/*
pdqsort.h - Pattern-defeating quicksort.
Copyright (c) 2015 Orson Peters
This software is provided 'as-is', without any express or implied warranty. In no event will the
authors be held liable for any damages arising from the use of this software.
Permission is granted to anyone to use this software for any purpose, including commercial
applications, and to alter it and redistribute it freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not claim that you wrote the
original software. If you use this software in a product, an acknowledgment in the product
documentation would be appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be misrepresented as
being the original software.
3. This notice may not be removed or altered from any source distribution.
*/
namespace pdqsort_detail {
enum {
// Partitions below this size are sorted using insertion sort.
insertion_sort_threshold = 24,
// Partitions above this size use Tukey's ninther to select the pivot.
ninther_threshold = 128,
// When we detect an already sorted partition, attempt an insertion sort that allows this
// amount of element moves before giving up.
partial_insertion_sort_limit = 8,
// Must be multiple of 8 due to loop unrolling, and < 256 to fit in unsigned char.
block_size = 64,
// Cacheline size, assumes power of two.
cacheline_size = 64
};
template<class T> struct is_default_compare : std::false_type { };
template<class T> struct is_default_compare<std::less<T>> : std::true_type { };
template<class T> struct is_default_compare<std::greater<T>> : std::true_type { };
// Returns floor(log2(n)), assumes n > 0.
template<class T>
inline int log2(T n) {
int log = 0;
while (n >>= 1) ++log;
return log;
}
// Sorts [begin, end) using insertion sort with the given comparison function.
template<class Iter, class Compare>
inline void insertion_sort(Iter begin, Iter end, Compare comp) {
typedef typename std::iterator_traits<Iter>::value_type T;
if (begin == end) return;
for (Iter cur = begin + 1; cur != end; ++cur) {
Iter sift = cur;
Iter sift_1 = cur - 1;
// Compare first so we can avoid 2 moves for an element already positioned correctly.
if (comp(*sift, *sift_1)) {
T tmp = std::move(*sift);
do { *sift-- = std::move(*sift_1); }
while (sift != begin && comp(tmp, *--sift_1));
*sift = std::move(tmp);
}
}
}
// Sorts [begin, end) using insertion sort with the given comparison function. Assumes
// *(begin - 1) is an element smaller than or equal to any element in [begin, end).
template<class Iter, class Compare>
inline void unguarded_insertion_sort(Iter begin, Iter end, Compare comp) {
typedef typename std::iterator_traits<Iter>::value_type T;
if (begin == end) return;
for (Iter cur = begin + 1; cur != end; ++cur) {
Iter sift = cur;
Iter sift_1 = cur - 1;
// Compare first so we can avoid 2 moves for an element already positioned correctly.
if (comp(*sift, *sift_1)) {
T tmp = std::move(*sift);
do { *sift-- = std::move(*sift_1); }
while (comp(tmp, *--sift_1));
*sift = std::move(tmp);
}
}
}
// Attempts to use insertion sort on [begin, end). Will return false if more than
// partial_insertion_sort_limit elements were moved, and abort sorting. Otherwise it will
// successfully sort and return true.
template<class Iter, class Compare>
inline bool partial_insertion_sort(Iter begin, Iter end, Compare comp) {
typedef typename std::iterator_traits<Iter>::value_type T;
if (begin == end) return true;
int limit = 0;
for (Iter cur = begin + 1; cur != end; ++cur) {
if (limit > partial_insertion_sort_limit) return false;
Iter sift = cur;
Iter sift_1 = cur - 1;
// Compare first so we can avoid 2 moves for an element already positioned correctly.
if (comp(*sift, *sift_1)) {
T tmp = std::move(*sift);
do { *sift-- = std::move(*sift_1); }
while (sift != begin && comp(tmp, *--sift_1));
*sift = std::move(tmp);
limit += cur - sift;
}
}
return true;
}
template<class Iter, class Compare>
inline void sort2(Iter a, Iter b, Compare comp) {
if (comp(*b, *a)) std::iter_swap(a, b);
}
// Sorts the elements *a, *b and *c using comparison function comp.
template<class Iter, class Compare>
inline void sort3(Iter a, Iter b, Iter c, Compare comp) {
sort2(a, b, comp);
sort2(b, c, comp);
sort2(a, b, comp);
}
template<class T>
inline T* align_cacheline(T* p) {
std::size_t ip = reinterpret_cast<std::size_t>(p);
ip = (ip + cacheline_size - 1) & -cacheline_size;
return reinterpret_cast<T*>(ip);
}
template<class Iter>
inline void swap_offsets(Iter first, Iter last,
unsigned char* offsets_l, unsigned char* offsets_r,
int num, bool use_swaps) {
typedef typename std::iterator_traits<Iter>::value_type T;
if (use_swaps) {
// This case is needed for the descending distribution, where we need
// to have proper swapping for pdqsort to remain O(n).
for (int i = 0; i < num; ++i) {
std::iter_swap(first + offsets_l[i], last - offsets_r[i]);
}
} else if (num > 0) {
Iter l = first + offsets_l[0]; Iter r = last - offsets_r[0];
T tmp(std::move(*l)); *l = std::move(*r);
for (int i = 1; i < num; ++i) {
l = first + offsets_l[i]; *r = std::move(*l);
r = last - offsets_r[i]; *l = std::move(*r);
}
*r = std::move(tmp);
}
}
// Partitions [begin, end) around pivot *begin using comparison function comp. Elements equal
// to the pivot are put in the right-hand partition. Returns the position of the pivot after
// partitioning and whether the passed sequence already was correctly partitioned. Assumes the
// pivot is a median of at least 3 elements and that [begin, end) is at least
// insertion_sort_threshold long. Uses branchless partitioning.
template<class Iter, class Compare>
inline std::pair<Iter, bool> partition_right_branchless(Iter begin, Iter end, Compare comp) {
typedef typename std::iterator_traits<Iter>::value_type T;
// Move pivot into local for speed.
T pivot(std::move(*begin));
Iter first = begin;
Iter last = end;
// Find the first element greater than or equal than the pivot (the median of 3 guarantees
// this exists).
while (comp(*++first, pivot));
// Find the first element strictly smaller than the pivot. We have to guard this search if
// there was no element before *first.
if (first - 1 == begin) while (first < last && !comp(*--last, pivot));
else while ( !comp(*--last, pivot));
// If the first pair of elements that should be swapped to partition are the same element,
// the passed in sequence already was correctly partitioned.
bool already_partitioned = first >= last;
if (!already_partitioned) {
std::iter_swap(first, last);
++first;
}
// The following branchless partitioning is derived from "BlockQuicksort: How Branch
// Mispredictions don’t affect Quicksort" by Stefan Edelkamp and Armin Weiss.
unsigned char offsets_l_storage[block_size + cacheline_size];
unsigned char offsets_r_storage[block_size + cacheline_size];
unsigned char* offsets_l = align_cacheline(offsets_l_storage);
unsigned char* offsets_r = align_cacheline(offsets_r_storage);
int num_l, num_r, start_l, start_r;
num_l = num_r = start_l = start_r = 0;
while (last - first > 2 * block_size) {
// Fill up offset blocks with elements that are on the wrong side.
if (num_l == 0) {
start_l = 0;
Iter it = first;
for (unsigned char i = 0; i < block_size;) {
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
}
}
if (num_r == 0) {
start_r = 0;
Iter it = last;
for (unsigned char i = 0; i < block_size;) {
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
}
}
// Swap elements and update block sizes and first/last boundaries.
int num = std::min(num_l, num_r);
swap_offsets(first, last, offsets_l + start_l, offsets_r + start_r,
num, num_l == num_r);
num_l -= num; num_r -= num;
start_l += num; start_r += num;
if (num_l == 0) first += block_size;
if (num_r == 0) last -= block_size;
}
int l_size = 0, r_size = 0;
int unknown_left = (last - first) - ((num_r || num_l) ? block_size : 0);
if (num_r) {
// Handle leftover block by assigning the unknown elements to the other block.
l_size = unknown_left;
r_size = block_size;
} else if (num_l) {
l_size = block_size;
r_size = unknown_left;
} else {
// No leftover block, split the unknown elements in two blocks.
l_size = unknown_left/2;
r_size = unknown_left - l_size;
}
// Fill offset buffers if needed.
if (unknown_left && !num_l) {
start_l = 0;
Iter it = first;
for (unsigned char i = 0; i < l_size;) {
offsets_l[num_l] = i++; num_l += !comp(*it, pivot); ++it;
}
}
if (unknown_left && !num_r) {
start_r = 0;
Iter it = last;
for (unsigned char i = 0; i < r_size;) {
offsets_r[num_r] = ++i; num_r += comp(*--it, pivot);
}
}
int num = std::min(num_l, num_r);
swap_offsets(first, last, offsets_l + start_l, offsets_r + start_r, num, num_l == num_r);
num_l -= num; num_r -= num;
start_l += num; start_r += num;
if (num_l == 0) first += l_size;
if (num_r == 0) last -= r_size;
// We have now fully identified [first, last)'s proper position. Swap the last elements.
if (num_l) {
offsets_l += start_l;
while (num_l--) std::iter_swap(first + offsets_l[num_l], --last);
first = last;
}
if (num_r) {
offsets_r += start_r;
while (num_r--) std::iter_swap(last - offsets_r[num_r], first), ++first;
last = first;
}
// Put the pivot in the right place.
Iter pivot_pos = first - 1;
*begin = std::move(*pivot_pos);
*pivot_pos = std::move(pivot);
return std::make_pair(pivot_pos, already_partitioned);
}
// Partitions [begin, end) around pivot *begin using comparison function comp. Elements equal
// to the pivot are put in the right-hand partition. Returns the position of the pivot after
// partitioning and whether the passed sequence already was correctly partitioned. Assumes the
// pivot is a median of at least 3 elements and that [begin, end) is at least
// insertion_sort_threshold long.
template<class Iter, class Compare>
inline std::pair<Iter, bool> partition_right(Iter begin, Iter end, Compare comp) {
typedef typename std::iterator_traits<Iter>::value_type T;
// Move pivot into local for speed.
T pivot(std::move(*begin));
Iter first = begin;
Iter last = end;
// Find the first element greater than or equal than the pivot (the median of 3 guarantees
// this exists).
while (comp(*++first, pivot));
// Find the first element strictly smaller than the pivot. We have to guard this search if
// there was no element before *first.
if (first - 1 == begin) while (first < last && !comp(*--last, pivot));
else while ( !comp(*--last, pivot));
// If the first pair of elements that should be swapped to partition are the same element,
// the passed in sequence already was correctly partitioned.
bool already_partitioned = first >= last;
// Keep swapping pairs of elements that are on the wrong side of the pivot. Previously
// swapped pairs guard the searches, which is why the first iteration is special-cased
// above.
while (first < last) {
std::iter_swap(first, last);
while (comp(*++first, pivot));
while (!comp(*--last, pivot));
}
// Put the pivot in the right place.
Iter pivot_pos = first - 1;
*begin = std::move(*pivot_pos);
*pivot_pos = std::move(pivot);
return std::make_pair(pivot_pos, already_partitioned);
}
// Similar function to the one above, except elements equal to the pivot are put to the left of
// the pivot and it doesn't check or return if the passed sequence already was partitioned.
// Since this is rarely used (the many equal case), and in that case pdqsort already has O(n)
// performance, no block quicksort is applied here for simplicity.
template<class Iter, class Compare>
inline Iter partition_left(Iter begin, Iter end, Compare comp) {
typedef typename std::iterator_traits<Iter>::value_type T;
T pivot(std::move(*begin));
Iter first = begin;
Iter last = end;
while (comp(pivot, *--last));
if (last + 1 == end) while (first < last && !comp(pivot, *++first));
else while ( !comp(pivot, *++first));
while (first < last) {
std::iter_swap(first, last);
while (comp(pivot, *--last));
while (!comp(pivot, *++first));
}
Iter pivot_pos = last;
*begin = std::move(*pivot_pos);
*pivot_pos = std::move(pivot);
return pivot_pos;
}
template<class Iter, class Compare, bool Branchless>
inline void pdqsort_loop(Iter begin, Iter end, Compare comp, int bad_allowed, bool leftmost = true) {
typedef typename std::iterator_traits<Iter>::difference_type diff_t;
// Use a while loop for tail recursion elimination.
while (true) {
diff_t size = end - begin;
// Insertion sort is faster for small arrays.
if (size < insertion_sort_threshold) {
if (leftmost) insertion_sort(begin, end, comp);
else unguarded_insertion_sort(begin, end, comp);
return;
}
// Choose pivot as median of 3 or pseudomedian of 9.
diff_t s2 = size / 2;
if (size > ninther_threshold) {
sort3(begin, begin + s2, end - 1, comp);
sort3(begin + 1, begin + (s2 - 1), end - 2, comp);
sort3(begin + 2, begin + (s2 + 1), end - 3, comp);
sort3(begin + (s2 - 1), begin + s2, begin + (s2 + 1), comp);
std::iter_swap(begin, begin + s2);
} else sort3(begin + s2, begin, end - 1, comp);
// If *(begin - 1) is the end of the right partition of a previous partition operation
// there is no element in [begin, end) that is smaller than *(begin - 1). Then if our
// pivot compares equal to *(begin - 1) we change strategy, putting equal elements in
// the left partition, greater elements in the right partition. We do not have to
// recurse on the left partition, since it's sorted (all equal).
if (!leftmost && !comp(*(begin - 1), *begin)) {
begin = partition_left(begin, end, comp) + 1;
continue;
}
// Partition and get results.
std::pair<Iter, bool> part_result =
Branchless ? partition_right_branchless(begin, end, comp)
: partition_right(begin, end, comp);
Iter pivot_pos = part_result.first;
bool already_partitioned = part_result.second;
// Check for a highly unbalanced partition.
diff_t l_size = pivot_pos - begin;
diff_t r_size = end - (pivot_pos + 1);
bool highly_unbalanced = l_size < size / 8 || r_size < size / 8;
// If we got a highly unbalanced partition we shuffle elements to break many patterns.
if (highly_unbalanced) {
// If we had too many bad partitions, switch to heapsort to guarantee O(n log n).
if (--bad_allowed == 0) {
std::make_heap(begin, end, comp);
std::sort_heap(begin, end, comp);
return;
}
if (l_size >= insertion_sort_threshold) {
std::iter_swap(begin, begin + l_size / 4);
std::iter_swap(pivot_pos - 1, pivot_pos - l_size / 4);
if (l_size > ninther_threshold) {
std::iter_swap(begin + 1, begin + (l_size / 4 + 1));
std::iter_swap(begin + 2, begin + (l_size / 4 + 2));
std::iter_swap(pivot_pos - 2, pivot_pos - (l_size / 4 + 1));
std::iter_swap(pivot_pos - 3, pivot_pos - (l_size / 4 + 2));
}
}
if (r_size >= insertion_sort_threshold) {
std::iter_swap(pivot_pos + 1, pivot_pos + (1 + r_size / 4));
std::iter_swap(end - 1, end - r_size / 4);
if (r_size > ninther_threshold) {
std::iter_swap(pivot_pos + 2, pivot_pos + (2 + r_size / 4));
std::iter_swap(pivot_pos + 3, pivot_pos + (3 + r_size / 4));
std::iter_swap(end - 2, end - (1 + r_size / 4));
std::iter_swap(end - 3, end - (2 + r_size / 4));
}
}
} else {
// If we were decently balanced and we tried to sort an already partitioned
// sequence try to use insertion sort.
if (already_partitioned && partial_insertion_sort(begin, pivot_pos, comp)
&& partial_insertion_sort(pivot_pos + 1, end, comp)) return;
}
// Sort the left partition first using recursion and do tail recursion elimination for
// the right-hand partition.
pdqsort_loop<Iter, Compare, Branchless>(begin, pivot_pos, comp, bad_allowed, leftmost);
begin = pivot_pos + 1;
leftmost = false;
}
}
}
template<class Iter, class Compare>
inline void pdqsort(Iter begin, Iter end, Compare comp) {
if (begin == end) return;
pdqsort_detail::pdqsort_loop<Iter, Compare,
pdqsort_detail::is_default_compare<typename std::decay<Compare>::type>::value &&
std::is_arithmetic<typename std::iterator_traits<Iter>::value_type>::value>(
begin, end, comp, pdqsort_detail::log2(end - begin));
}
template<class Iter>
inline void pdqsort(Iter begin, Iter end) {
typedef typename std::iterator_traits<Iter>::value_type T;
pdqsort(begin, end, std::less<T>());
}
template<class Iter, class Compare>
inline void pdqsort_branchless(Iter begin, Iter end, Compare comp) {
if (begin == end) return;
pdqsort_detail::pdqsort_loop<Iter, Compare, true>(
begin, end, comp, pdqsort_detail::log2(end - begin));
}
template<class Iter>
inline void pdqsort_branchless(Iter begin, Iter end) {
typedef typename std::iterator_traits<Iter>::value_type T;
pdqsort_branchless(begin, end, std::less<T>());
}
const f64 TL = 0.99;
timer TM;
const i32 N = 45;
i64 A[N], B[N];
void read(){
i32 n; cin>>n; do { if(!(n == N)) { throw runtime_error("main.cpp" ":" "11" " Assertion failed: " "n == N"); } } while(0);
for(i32 i = 0; i < (i32)(N); ++i) cin>>A[i]>>B[i];
}
struct p2 {
i64 x,y;
i64 m;
p2(i64 x_, i64 y_, i64 m_){
x = x_;
y = y_;
m = m_;
}
p2() {
x = y = m = 0;
}
p2& operator+=(p2 const& o) {
x += o.x;
y += o.y;
m |= o.m;
return *this;
}
p2 operator+(p2 const& o) const{
p2 r = *this; r += o; return r;
}
};
vector<p2> merge(vector<p2> const& A, vector<p2> const& B){
i64 ia = 0, ib = 0;
i64 na = A.size(), nb = B.size();
vector<p2> out; out.reserve(na+nb);
while(ia<na && ib<nb) {
if(A[ia].x<B[ib].x) { out.emplace_back(A[ia]); ia++; }
else { out.emplace_back(B[ib]); ib++; }
}
while(ia<na) { out.emplace_back(A[ia]); ia++; }
while(ib<nb) { out.emplace_back(B[ib]); ib++; }
return out;
}
vector<p2> build(vector<p2> X) {
vector<p2> Y = {p2()};
for(auto const& x : X) {
auto L = Y, R = Y;
for(auto& p : R) p += x;
Y = merge(L, R);
}
return Y;
}
template<typename V, typename Pred>
void filter(V &v, Pred pred) {
i32 sz = 0;
for(i32 i = 0; i < (i32)(v.size()); ++i) if(pred(v[i])) {
v[sz++] = v[i];
}
v.resize(sz);
}
void print_answer(vector<array<i32,2>> ans) {
cout << ans.size() << endl;
for(auto [x,y] : ans) {
cout << 1+x << " " << 1+y << endl;
}
}
f64 GOAL = 5e17;
struct llist {
i32 elem;
i32 nxt;
};
const i32 LLIST_POOL_SIZE = 1<<24;
llist llist_pool[LLIST_POOL_SIZE];
i32 llist_pool_next = 0;
i32 make_llist(i32 e, i32 n) {
llist_pool[llist_pool_next] = llist {e,n};
return llist_pool_next++;
}
struct state {
f64 valuea, valueb;
u64 available;
f64 suma_available;
f64 sumb_available;
f64 heur_value;
i32 history;
void reset()
{
valuea = GOAL;
valueb = GOAL;
available = (1ll<<N)-1;
suma_available = 0;
sumb_available = 0;
for(i32 i = 0; i < (i32)(N); ++i) suma_available += A[i];
for(i32 i = 0; i < (i32)(N); ++i) sumb_available += B[i];
history = -1;
}
void step(i32 i) {
valuea = (valuea-(f64)A[i]/2) * 2.0;
valueb = (valueb-(f64)B[i]/2) * 2.0;
suma_available -= A[i];
sumb_available -= B[i];
available ^= (1ll<<i);
calc_heur();
history = make_llist(i, history);
}
void calc_heur() {
i32 n = __builtin_popcountll(available);
heur_value = max(abs(valuea-suma_available/n), abs(valueb-sumb_available/n));
}
vector<i32> recon() const {
vector<i32> I;
for(i32 i = 0; i < (i32)(N); ++i) if(available&(1ll<<i)) I.emplace_back(i);
for(i32 h = history; h != -1; h = llist_pool[h].nxt) {
I.emplace_back(llist_pool[h].elem);
}
return I;
}
};
const i32 BASE_WIDTH = 11'500;
void solve(){
vector<state> beam(1); beam[0].reset();
for(i32 step = 0; step < (i32)(N-2); ++step) {
i32 WIDTH = BASE_WIDTH;
if(step > N-10) WIDTH *= 4;
auto t_now = TM.elapsed();
vector<state> nbeam; nbeam.reserve(beam.size() * (N-step));
for(auto const& sa : beam) {
for(i32 i = 0; i < (i32)(N); ++i) if(sa.available&(1ll<<i)) {
auto sb = sa;
sb.step(i);
nbeam.emplace_back(sb);
}
}
beam = move(nbeam);
rng.shuffle(beam);
if(beam.size() > WIDTH) {
nth_element(begin(beam), begin(beam)+WIDTH, end(beam), [&](auto const& a, auto const& b) { return a.heur_value < b.heur_value; });
beam.resize(WIDTH);
}
}
i64 best_score = 1e18;
vector<i32> best_I;
i32 iter = 0;
for(auto const& s : beam) {
iter++;
if(iter % 1024 == 0 && TM.elapsed() > TL) break;
auto I = s.recon();
i64 a = A[I[0]], b = B[I[0]];
for(i32 i = (1); i <= (i32)(N-1); ++i) {
a = (a+A[I[i]])/2;
b = (b+B[I[i]])/2;
}
i64 score = max(abs(a-GOAL), abs(b-GOAL));
if(score < best_score) {
best_score = score;
do { cerr << "main.cpp" ":" "181" " {" << "iter, best_score" << "} = {"; debug_impl_seq(iter, best_score); cerr << endl << flush; } while(0);
best_I = I;
}
}
vector<array<i32,2>> ans;
for(i32 i = (0); i <= (i32)(N-2); ++i) {
ans.push_back({best_I[i],best_I[i+1]});
best_I[i+1] = min(best_I[i], best_I[i+1]);
}
cerr << "Elapsed: " << TM.elapsed() << endl;
cerr << "[DATA] time = " << TM.elapsed() << endl;
print_answer(ans);
}
i32 main(){
// llist_pool = new llist[LLIST_POOL_SIZE];
ios::sync_with_stdio(false); cin.tie(0);
TM.reset();
read();
solve();
return 0;
}