Зниклий інтернет Неру#12447
Увійти

Зниклий інтернет Неру (Розбір)

Автор задачі:

Деркач Тарас

Підготував:

Деркач Тарас

Розбір:

Деркач Тарас

Розв'язання

Спочатку порахуємо початкове значення з'єднання:

(p_1 \oplus p_2) + (p_2 \oplus p_3) + \ldots + (p_{n-1} \oplus p_n).

Далі будемо шукати не саме нове значення, а максимальне збільшення після двох перестановок.

Розглянемо один відрізок довжини , який починається в позиції .

Після перестановки елементів на цьому відрізку змінюються тільки ребра біля цього відрізка:

(s-1,s), (s,s+1), (s+1,s+2), (s+2,s+3), (s+3,s+4).

Якщо якогось ребра не існує через межу масиву, ми його просто не враховуємо.

Оскільки довжина відрізка дорівнює , можна перебрати всі його перестановки. Їх всього 4! = 24.

Для кожного початку порахуємо delta_s — максимальне збільшення значення, якщо переставити тільки відрізок [s,s+3].

Тепер потрібно вибрати два відрізки.

Є два випадки.

Перший випадок: між відрізками є хоча б одна позиція.

Якщо перший відрізок починається в , а другий у , і j-i \ge 5, то ребра, на які вони впливають, не перетинаються.

Тому загальне збільшення дорівнює:

delta_i + delta_j.

Щоб швидко знайти максимум, будемо підтримувати префіксний максимум для delta_i.

Другий випадок: відрізки стоять впритул.

Це випадок, коли j=i+4.

Тоді відрізки не перетинаються, але між ними є спільне ребро:

(i+3,i+4).

Це ребро залежить від обох перестановок одночасно, тому не можна просто додати delta_i + delta_j.

Для цього випадку окремо збережемо допоміжні значення.

Для кожного відрізка будемо знати:

Тоді для двох сусідніх відрізків переберемо тільки те, який елемент стоїть останнім у першому відрізку і який елемент стоїть першим у другому відрізку. Таких варіантів всього 4 \cdot 4.

Після цього відповідь дорівнює початковому значенню плюс максимальне знайдене збільшення.

Приклад

У першому прикладі можна обрати відрізки та .

Після переставлення масив може стати:

[1,2,4,3,5,6,8,7].

Тоді значення з'єднання дорівнює:

(1 \oplus 2) + (2 \oplus 4) + (4 \oplus 3) + (3 \oplus 5) + (5 \oplus 6) + (6 \oplus 8) + (8 \oplus 7) = 54.

Асимптотика

Для кожного відрізка довжини ми перебираємо перестановки.

Для сусідніх відрізків додатково перебираємо 4 \cdot 4 варіантів.

Усі ці числа є константами, тому загальна складність розв'язання становить .

Розв'язок

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = (ll)4e18;

void solve() {
    int n;
    cin >> n;

    vector<ll> p(n);

    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    vector<array<int, 4>> perms;
    array<int, 4> cur = {0, 1, 2, 3};

    do {
        perms.push_back(cur);
    } while (next_permutation(cur.begin(), cur.end()));

    vector<ll> pref(n, 0);

    for (int i = 0; i + 1 < n; i++) {
        pref[i + 1] = pref[i] + (p[i] ^ p[i + 1]);
    }

    auto get_sum = [&](int l, int r) -> ll {
        l = max(l, 0);
        r = min(r, n - 2);

        if (l > r) {
            return 0;
        }

        return pref[r + 1] - pref[l];
    };

    ll base = pref[n - 1];

    int m = n - 3;

    vector<ll> delta(m);
    vector<array<ll, 4>> left_best(m), right_best(m);

    for (int s = 0; s < m; s++) {
        for (int i = 0; i < 4; i++) {
            left_best[s][i] = -INF;
            right_best[s][i] = -INF;
        }

        ll old_value = get_sum(s - 1, s + 3);
        ll best_value = -INF;

        for (auto perm : perms) {
            ll a = p[s + perm[0]];
            ll b = p[s + perm[1]];
            ll c = p[s + perm[2]];
            ll d = p[s + perm[3]];

            ll inside = (a ^ b) + (b ^ c) + (c ^ d);

            ll value = inside;

            if (s > 0) {
                value += (p[s - 1] ^ a);
            }

            if (s + 4 < n) {
                value += (d ^ p[s + 4]);
            }

            best_value = max(best_value, value);

            ll left_value = inside;

            if (s > 0) {
                left_value += (p[s - 1] ^ a);
            }

            ll right_value = inside;

            if (s + 4 < n) {
                right_value += (d ^ p[s + 4]);
            }

            left_best[s][perm[3]] = max(left_best[s][perm[3]], left_value);
            right_best[s][perm[0]] = max(right_best[s][perm[0]], right_value);
        }

        delta[s] = best_value - old_value;
    }

    ll best_not_adjacent = -INF;
    ll pref_best = -INF;

    for (int second = 0; second < m; second++) {
        if (second >= 5) {
            pref_best = max(pref_best, delta[second - 5]);
            best_not_adjacent = max(best_not_adjacent, pref_best + delta[second]);
        }
    }

    ll best_adjacent = -INF;

    for (int first = 0; first + 4 < m; first++) {
        int second = first + 4;

        ll best_value = -INF;

        for (int last_first = 0; last_first < 4; last_first++) {
            for (int first_second = 0; first_second < 4; first_second++) {
                ll value = left_best[first][last_first];
                value += (p[first + last_first] ^ p[second + first_second]);
                value += right_best[second][first_second];

                best_value = max(best_value, value);
            }
        }

        ll old_value = get_sum(first - 1, first + 7);

        best_adjacent = max(best_adjacent, best_value - old_value);
    }

    ll best_gain = max(best_adjacent, best_not_adjacent);

    cout << base + best_gain << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}