Submission #1206969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206969		friendiks	Rotating Lines (APIO25_rotate)	C++20	11 / 100	60 ms	6984 KiB

rotate

#ifndef LOCAL
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC diagnostic ignored "-Wpedantic"
#endif

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

using namespace std;
using namespace __gnu_pbds;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(52);
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename V>
using table = gp_hash_table<T, V>;

using i128 = __int128;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;

const ll INF = 2e18;
const int inf = 2e9;
const int maxn = 1e5;
const int MOD = 988244353;
const ld pi = acos(-1);
const int P = 5167;
const int L = 26;
const ld EPS = 1e-7;

template<typename T, typename V>
void fill(T &container, V value) {
    for (auto &c: container)
        c = value;
}

ll calculate_acute_value(int val1, int val2) {
    ll diff_abs = abs(static_cast<ll>(val1) - val2);
    ll val = min(diff_abs, 50000LL - diff_abs);
    return val;
}

void rotate(vector<int> t, int x);

void energy(int n, vector<int> v_initial) {
    vector<int> v = v_initial;
    ll total_rods_selected_count = 0;
    if (n <= 2000) {
        for (int pass = 0; pass < 3; ++pass) {
            bool changed_in_pass = false;
            if (total_rods_selected_count >= 2000000) break;

            for (int i = 0; i < n; ++i) {
                if (total_rods_selected_count >= 2000000) break;

                int current_vi = v[i];
                int target_T;

                ll dist_to_0 = calculate_acute_value(current_vi, 0);
                ll dist_to_25000 = calculate_acute_value(current_vi, 25000);

                if (dist_to_0 <= dist_to_25000) {
                    target_T = 0;
                } else {
                    target_T = 25000;
                }

                if (current_vi == target_T) {
                    continue;
                }

                int rotation_x = (target_T - current_vi + 50000) % 50000;

                ll delta_E = 0;
                for (int j = 0; j < n; ++j) {
                    if (i == j) continue;
                    ll old_acute_ij = calculate_acute_value(current_vi, v[j]);
                    ll new_acute_ij = calculate_acute_value(target_T, v[j]);
                    delta_E += (new_acute_ij - old_acute_ij);
                }

                if (delta_E >= 0) {
                    if (total_rods_selected_count + 1 <= 2000000) {
                        rotate({i}, rotation_x);
                        v[i] = target_T;
                        total_rods_selected_count++;
                        changed_in_pass = true;
                    } else {
                        return;
                    }
                }
            }
            if (!changed_in_pass) {
                break;
            }
        }
    } else {
        vector<pair<ll, int>> preferences(n);
        for (int i = 0; i < n; ++i) {
            ll dist_to_0 = calculate_acute_value(v[i], 0);
            ll dist_to_25000 = calculate_acute_value(v[i], 25000);
            preferences[i] = {dist_to_0 - dist_to_25000, i};
        }
        sort(preferences.begin(), preferences.end());

        vector<int> targets(n);
        int count_for_pole_0 = n / 2;
        for (int k = 0; k < count_for_pole_0; ++k) {
            targets[preferences[k].second] = 0;
        }
        for (int k = count_for_pole_0; k < n; ++k) {
            targets[preferences[k].second] = 25000;
        }

        map<int, vector<int>> rotations_to_perform;
        for (int i = 0; i < n; ++i) {
            if (v[i] == targets[i]) continue;
            int rotation_x = (targets[i] - v[i] + 50000) % 50000;
            if (rotation_x == 0) continue;
            rotations_to_perform[rotation_x].push_back(i);
        }
        for (auto const& pair_rot_indices : rotations_to_perform) {
            int rot_val = pair_rot_indices.first;
            const vector<int>& indices = pair_rot_indices.second;

            if (indices.empty()) continue;
            if (total_rods_selected_count + indices.size() <= 2000000) {
                rotate(indices, rot_val);
                total_rods_selected_count += indices.size();
                for (int rod_idx : indices) {
                    v[rod_idx] = targets[rod_idx];
                }
            } else {
                for (int rod_idx : indices) {
                    if (total_rods_selected_count + 1 <= 2000000) {
                        rotate({rod_idx}, rot_val);
                        v[rod_idx] = targets[rod_idx];
                        total_rods_selected_count++;
                    } else {
                        return;
                    }
                }
            }
            if (total_rods_selected_count >= 2000000) return;
        }
    }
}

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