#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;
//Class to operate Timsort process
template <typename t_it, typename comparator>
class tim_sorting{
public:
tim_sorting (const t_it& l, const t_it& r, const comparator& custom) : cmp(custom) {
//Ranges with size 0-1 are already sorted
if (r-l<=1)
return;
//Calculate appropriate min run size based on data size
find_min_run_size(r-l);
//Initialize the start of the first run at l
t_it run_l=l;
//Runs stack storing runs in format {l,size}
vector<pair<t_it,size_t>> runs;
//Whilst theres still elements remaining
while (run_l!=r){
//Find the end of the current run
size_t run_size=find_run_size(run_l,r);
//If the run is too short, extend it using Insertion Sort
if (run_size<min_run_size){
run_size=min<size_t>(min_run_size,r-run_l);
insertion_sort(run_l,run_l+run_size);
}
//Add current run to stack
runs.push_back({run_l,run_size});
//Advance left pointer to find next run
run_l+=run_size;
//Check Timsort stack invariants
while (runs.size()>1){
size_t n=runs.size()-2;
//Invariant 1: |Z|>|X|+|Y|
if (n>0 && runs[n-1].second<=runs[n].second+runs[n+1].second || n>1 && runs[n-2].second<=runs[n].second+runs[n-1].second){
//Select smaller of X and Z
if (runs[n-1].second<runs[n+1].second)
--n;
}
//Invariant 2: |Y|>|X|
else if (n<0 || runs[n].second>runs[n+1].second)
break;
//Merge Y with smaller of X and Z
compressed_merge(runs[n].first,runs[n].first+runs[n].second,runs[n+1].first+runs[n+1].second);
//Update ranges to signify merge occured
runs[n].second+=runs[n+1].second;
if (n==runs.size()-3)
runs[n+1]=runs[n+2];
runs.pop_back();
}
}
//Merge all remaining ranges
while (runs.size()>1){
size_t n=runs.size()-2;
//Select smaller of X and Z (if Z exists)
if (n>0 && runs[n-1].second<runs[n+1].second)
--n;
//Merge Y with smaller of X and Z
compressed_merge(runs[n].first,runs[n].first+runs[n].second,runs[n+1].first+runs[n+1].second);
//Update ranges to signify merge occured
runs[n].second+=runs[n+1].second;
if (n==runs.size()-3)
runs[n+1]=runs[n+2];
runs.pop_back();
}
}
private:
//Minimum size of runs
size_t min_run_size;
//Value type of iterators
using t_type=iterator_traits<t_it>::value_type;
//Comparison function, definition of less
const comparator& cmp;
//Function to calculate suitable min run size for n elements
void find_min_run_size (size_t n);
//Function to reverse the range [l,r-1] for descending runs
void reverse_range (t_it l, t_it r);
//Function to find the size of a run starting at l
size_t find_run_size (const t_it& l, const t_it& r);
//Function to rotate the range [l,r-1] n places to the left
void rotate_range (const t_it& l, const t_it& r, const size_t& n);
//Function that conducts Insertion Sort to extend short runs
void insertion_sort (const t_it& l, const t_it& r);
//Function to compress merging range
void compressed_merge (const t_it& l, const t_it& mid, const t_it& r);
//Dynamically merges ranges [l,mid-1] and [mid,r-1], partitioning if nessacary
void dynamic_merge (const t_it& l, const t_it& mid, const t_it& r);
//Function that merges ranges [l,mid-1] and [mid,r-1] left to right
void forward_merge (const t_it& l, const t_it& mid, const t_it& r, t_type* a_buffer);
//Function that merges ranges [l,mid-1] and [mid,r-1] right to left
void backward_merge (const t_it& l, const t_it& mid, const t_it& r, t_type* b_buffer);
};
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::find_min_run_size (size_t n){
//Gets the first 6 bits of n, ensuring n/run_size is close to a power of 2 for efficient merging
bool r=0;
while (n>=64){
r|=n&1;
n>>=1;
}
min_run_size=n+r;
}
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::reverse_range (t_it l, t_it r){
//Find middle point
t_it mid=l+((r-l)>>1);
//As r is the iterator to the element after the last element, decrement it so it points to the last element
--r;
//Use two pointers method to reverse range using swaps
while (l!=mid){
swap(*l,*r);
++l;
--r;
}
}
template <typename t_it, typename comparator>
size_t tim_sorting<t_it,comparator>::find_run_size (const t_it& l, const t_it& r){
t_it pos=l+1,end=r-1;
//Bounds check
if (l==end)
return 1;
//Check if run is non-descending or descending
bool descending=cmp(*pos,*l) ? 1 : 0;
if (descending){
//Extend run whilst it remains descending
while (pos!=end && cmp(*(pos+1),*pos))
++pos;
++pos;
//Reverse descending run so it is non-ascending
reverse_range(l,pos);
}
else{
//Extend run whilst it remains non-descending
while (pos!=end && !cmp(*(pos+1),*pos))
++pos;
++pos;
}
return pos-l;
}
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::rotate_range (const t_it& l, const t_it& r, const size_t& n){
//Execute rotation using 3 reversals
reverse_range(l,r);
reverse_range(l,l+n);
reverse_range(l+n,r);
}
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::insertion_sort (const t_it& l, const t_it& r){
//Start from the second element, as the first element on its own is trivially sorted
for (t_it i=l+1; i!=r; ++i){
t_type temp=move(*i);
t_it j=i;
//Insert element into sorted range on the left
while (j!=l && cmp(temp,*(j-1))){
*j=move(*(j-1));
--j;
}
*j=move(temp);
}
}
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::compressed_merge(const t_it& l, const t_it& mid, const t_it& r) {
//Range A: [l,mid-1]; Range B: [mid,r-1]
size_t l_l=0,l_r=mid-l-1,r_l=0,r_r=r-mid-1;
t_type l_ref=*mid,r_ref=*(mid-1);
//Find the position (l+l_l) of the first element in A greater than the smallest/first element in B. No elements in B will go before l+l_l, meaning [l,l+l_l-1] will not move in the merge.
while (l_l<l_r){
size_t l_mid=(l_l+l_r+1)>>1;
if (cmp(l_ref,*(l+l_mid)))
l_r=l_mid-1;
else
l_l=l_mid;
}
//Handle edge case where *mid<*l
if (!cmp(l_ref,*(l+l_l)))
++l_l;
//Find the position (mid+r_l) of the first element in B greater or equal to the greatest/last element in A. No elements in A will go after mid+r_l, meaning [mid+r_l,r-1] will not move in the merge.
while (r_l<r_r){
size_t r_mid=(r_l+r_r)>>1;
if (cmp(*(mid+r_mid),r_ref))
r_l=r_mid+1;
else
r_r=r_mid;
}
//Handle edge case where *(mid-1)>*(r-1)
if (cmp(*(mid+r_l),r_ref))
++r_l;
//As [l,l+l_l-1] and [mid+r_l,r-1] will not move during the merge, they can be excluded from the merge. Choose appropriate merge direction to minimize buffer size.
dynamic_merge(l+l_l,mid,mid+r_l);
}
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::dynamic_merge (const t_it& l, const t_it& mid, const t_it& r){
//Choose direction to minimize buffer size and copying
if (mid-l>r-mid){
//Attempt to allocate buffer for standard merge
unique_ptr<t_type[]> buffer(new(std::nothrow) t_type[r-mid]);
//If buffer allocation succeeds, proceed with standard merge
if (buffer)
backward_merge(l,mid,r,buffer.get());
//If buffer allocation fails due to lack of space, execute 1 pass of rotate merge to halve space requirement
else{
//Split larger range into uniform halves
t_it pivot=l+(mid-l>>1);
size_t r_l=0,r_r=r-mid-1;
//Bianry search for split point in smaller range
while (r_l<r_r){
size_t r_mid=(r_l+r_r)>>1;
if (cmp(*(mid+r_mid),*pivot))
r_l=r_mid+1;
else
r_r=r_mid;
}
if (cmp(*(mid+r_l),*pivot))
++r_l;
//Partition using rotation, reducing the merge operation into two smaller merges
rotate_range(pivot,mid+r_l,r_l);
//Recursivley merge smaller ranges, excluding the pivot
dynamic_merge(l,pivot,pivot+r_l);
dynamic_merge(pivot+r_l+1,mid+r_l,r);
}
}
else{
//If buffer allocation fails due to lack of space, execute 1 pass of rotate merge to halve space requirement
unique_ptr<t_type[]> buffer(new(nothrow) t_type[mid-l]);
//If buffer allocation succeeds, proceed with standard merge
if (buffer)
forward_merge(l,mid,r,buffer.get());
//If buffer allocation fails due to lack of space, fall back to rotate merge
else{
//Split larger range into uniform halves
t_it pivot=mid+(r-mid>>1);
size_t l_l=0,l_r=mid-l-1;
//Bianry search for split point in smaller range
while (l_l<l_r){
size_t l_mid=(l_l+l_r+1)>>1;
if (cmp(*pivot,*(l+l_mid)))
l_r=l_mid-1;
else
l_l=l_mid;
}
if (!cmp(*pivot,*(l+l_l)))
++l_l;
++pivot;
//Reuse l_r to store new size of A range after partition
l_r=pivot-mid+l_l;
//Partition using rotation, reducing the merge operation into two smaller merges
rotate_range(l+l_l,pivot,pivot-mid);
//Recursivley merge smaller ranges, excluding the pivot
dynamic_merge(l,l+l_l,l+l_r-1);
dynamic_merge(l+l_r,pivot,r);
}
}
}
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::forward_merge (const t_it& l, const t_it& mid, const t_it& r, t_type* a_buffer){
//Copy Range A into a_buffer
size_t a=0,a_r=mid-l;
for (t_it it=l; it!=mid; ++it){
a_buffer[a]=*it;
++a;
}
//Merge from left to right, initializing pointers on left
t_it pos=l,b=mid;
a=0;
//Whilst both ranges are not empty
while (a!=a_r && b!=r){
//Select the smaller element from range A and B and place into position, prioritizing A over B during ties to ensure stability
if (cmp(*b,a_buffer[a])){
*pos=move(*b);
++b;
}
else{
*pos=move(a_buffer[a]);
++a;
}
//Move pos right for the next element
++pos;
}
//After one range is empty, copy all the items of the remaining range back into the main container
while (a!=a_r){
*pos=move(a_buffer[a]);
++a;
++pos;
}
//Notice there is no need to handle remaining items in range B, as they are already in the correct location
}
template <typename t_it, typename comparator>
void tim_sorting<t_it,comparator>::backward_merge (const t_it& l, const t_it& mid, const t_it& r, t_type* b_buffer){
//Copy range B into b_buffer
size_t b=0,b_r=-1;
for (t_it it=mid; it!=r; ++it){
b_buffer[b]=*it;
++b;
}
//Merge from right to left, initializing pointers on right
t_it pos=r-1,a=mid-1,a_r=l-1;
b=r-mid-1;
//Whilst both ranges are not empty
while (a!=a_r && b!=b_r){
//Select the larger element from range A and B and place into position, prioritizing B over A during ties to ensure stability
if (cmp(b_buffer[b],*a)){
*pos=move(*a);
--a;
}
else{
*pos=move(b_buffer[b]);
--b;
}
//Move pos left for next element
--pos;
}
//After one range is empty, copy all the items of the remaining range back into the main container
while (b!=b_r){
*pos=move(b_buffer[b]);
--b;
--pos;
}
//Notice there is no need to handle remaining items in range A, as they are already in the correct location
}
//Overloaded wrapper function to handle situation with and without custom comparator
template <typename t_it>
void tim_sort (const t_it& l, const t_it& r){
using t_type=iterator_traits<t_it>::value_type;
//Default to std::less if no custom comparator is given
tim_sorting instance(l,r,less<t_type>());
}
template <typename t_it, typename comparator>
void tim_sort (const t_it& l, const t_it& r, const comparator& cmp){
//Pass custom comparator to class
tim_sorting instance(l,r,cmp);
}
bool cmp (const pair<int,int>& a, const pair<int,int>& b){
return a.first<b.first;
}
void energy(int n, vector<int> v){
vector<pair<int,int>> v2(n);
for (size_t i=0; i<n; i++)
v2[i]={v[i],i};
tim_sort(v2.begin(),v2.end(),cmp);
n>>=1;
for (size_t i=0; i<n; i++)
rotate({v2[i+n].second},v2[i].first+25000-v2[i+n].first);
}
