Submission #1223381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223381		dizzy_groovy	Rotating Lines (APIO25_rotate)	C++20	100 / 100	87 ms	8008 KiB

rotate

#include "rotate.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/*int energy(int v, vector<int> &pref_l, vector<int> &pref_r, int cnt0, int cnt90, int l, int r) {
    
}*/

long long my_calc_energy(vector<int> &v){
    long long res = 0;
    for (int i = 0; i < (int) v.size(); i++){
        for (int j = i + 1; j < (int) v.size(); j++){
            int d = abs(v[i] - v[j]);
            res += std::min(d, 50000 - d);
        }
    }
    return res;
}

void energy(int n, std::vector<int> v) {
    ordered_set<pair<int, int>> v2;
    for (int i = 0; i < n; i++) {
        //v[i] = (v[i] - mi);
        //cout << i << endl;
        if (v2.lower_bound({(v[i] + 25000) % 50000, -1}) == v2.end() || v2.lower_bound({(v[i] + 25000) % 50000, -1})->first != ((v[i] + 25000) % 50000)) {
            v2.insert({v[i], i});
        } else {
            v2.erase(v2.lower_bound({(v[i] + 25000) % 50000, -1}));
        }
    }
    while (v2.size() > 1) {
        auto it = (*(v2.begin()));
        auto it2 = v2.find_by_order((v2.size()) / 2);
        auto tmp = (*it2);
        v2.erase(it);
        v2.erase(it2);
        rotate({tmp.second}, ((it.first + 75000 - tmp.first) % 50000));
    }
    return;
}

• 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