Submission #1253569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253569		noop	Rotating Lines (APIO25_rotate)	C++20	100 / 100	31 ms	2464 KiB

rotate

#include "rotate.h"
#include <bits/stdc++.h>
using namespace std;

template <typename t_it, typename comparator>
class heap_sorting{
    public:
        heap_sorting (const t_it& l, const t_it& r, const comparator& in) : cmp(in) , t(l-1), n(r-l) {
            for (size_t i=n>>1; i; --i){
                t_type temp=*(t+i);
                sift_down(i,temp);
            }
            while (--n){
                t_type temp=*(l+n);
                *(l+n)=*l;
                sift_down(1,temp);
            }
        }
    
    private:
        using t_type=iterator_traits<t_it>::value_type;
        
        const t_it& t;

        const comparator& cmp;
        
        size_t n;
        
        inline void sift_down (const size_t& root, const t_type& temp) {
            size_t pos=root,c=pos<<1;
            while (c<n){
                c+=cmp(*(t+c),*(t+c+1));
                if (cmp(temp,*(t+c))){
                    *(t+pos)=*(t+c);
                    pos=c;
                    c<<=1;
                }
                else
                    break;
            }
            if (c==n && cmp(temp,*(t+c))){
                *(t+pos)=*(t+c);
                pos=c;
            }
            *(t+pos)=temp;
        }
};

template <typename t_it>
void heap_sort (const t_it& l, const t_it& r) {
    heap_sorting instance(l,r,less<typename iterator_traits<t_it>::value_type>());
}

template <typename t_it, typename comparator>
void heap_sort (const t_it& l, const t_it& r, const comparator& cmp) {
    heap_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};
    heap_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);
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 26 / 26