Сдать решение задачи G-Кубики (2 балла) Ограничен...

Question

Сдать решение задачи G-Кубики (2 балла)

Ограничение времени: 1500 мс
Ограничение реального времени: 5 с
Ограничение памяти: 256M
Задача G: Кубики (2 балла)

Условие задачи (pdf)

Привидение Петя любит играть со своими кубиками. Он любит выкладывать их в ряд и разглядывать свое творение. Однако недавно друзья решили подшутить над Петей и поставили в его игровой комнате зеркало. Ведь всем известно, что привидения не отражаются в зеркале! А кубики отражаются. Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие — всего лишь отражение в зеркале. Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков, которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.

image

Формат входных данных

Первая строка входного файла содержит число N (1≤N≤106) и количество различных цветов, в которые могут быть раскрашены кубики — M (1≤M≤106). Следующая строка содержит N целых чисел от 1 до M — цвета кубиков.

Формат выходных данных

Выведите в выходной файл все такие K, что у Пети может быть K кубиков в подрядке возрастания

include <iostream>
#include <vector>
using namespace std;

using ll = long long;

const int MAXN = 2 * 1e6;
const int M = 1e9 + 7;
const int P = 313;

ll h[MAXN], rh[MAXN], p[MAXN];

ll get_hash(int l, int r) {
ll v = (h[r] - h[l - 1] * p[r - l + 1]) % M;
if (v < 0) v += M;
return v;
}

ll get_rhash(int l, int r) {
ll v = (rh[r] - rh[l - 1] * p[r - l + 1]) % M;
if (v < 0) v += M;
return v;
}

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

text
int n, m;
cin >> n >> m;

vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];

p[0] = 1;
for (int i = 1; i <= n; ++i) {
    p[i] = (p[i - 1] * P) % M;
    h[i] = (h[i - 1] * P + a[i]) % M;
    rh[i] = (rh[i - 1] * P + a[n - i + 1]) % M;
}

vector<int> ans;
for (int i = (n / 2; i <= n; i++) {
    int l2 = 1 + i;
    int r2 = min(2 * i, n);
    int len = r2 - l2 + 1;

    int r1 = i;
    int l1 = i - len + 1;

    ll v1 = get_hash(l1, r1);
    ll v2 = get_rhash(n - r2 + 1, n - l2 + 1);

    if (v1 == v2) ans.push_back(i);
}

for (auto u : ans) cout << u << ' ';
return 0;

}
что не так? исправь мой код, МИНИМАЛЬНО его изменяя и очень подробно все объясняя (отдельно объясни и продемонстрируй на примере работу предпоследнего цикла)

Answer 1

Вот минимально исправленный код:

cpp
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

const int MAXN = 2000005;
const int MOD = 1e9 + 7;
const int P = 313;

ll h[MAXN], rh[MAXN], p[MAXN];

ll get_hash(int l, int r) {
    if (l > r) return 0;
    ll v = (h[r] - h[l - 1] * p[r - l + 1]) % MOD;
    if (v < 0) v += MOD;
    return v;
}

ll get_rhash(int l, int r) {
    if (l > r) return 0;
    ll v = (rh[r] - rh[l - 1] * p[r - l + 1]) % MOD;
    if (v < 0) v += MOD;
    return v;
}

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

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = (p[i - 1] * P) % MOD;
        h[i] = (h[i - 1] * P + a[i]) % MOD;
        rh[i] = (rh[i - 1] * P + a[n - i + 1]) % MOD;
    }

    vector<int> ans;

    for (int i = (n + 1) / 2; i <= n; i++) {
        int l2 = i + 1;
        int r2 = n;
        int len = r2 - l2 + 1;

        int r1 = i;
        int l1 = i - len + 1;

        ll v1 = get_hash(l1, r1);
        ll v2 = get_rhash(n - r2 + 1, n - l2 + 1);

        if (v1 == v2) ans.push_back(i);
    }

    for (auto u : ans) cout << u << ' ';
    return 0;
}

Что было не так:

В первой строке не хватало #:

cpp
#include <iostream>

В цикле была синтаксическая ошибка:

cpp
for (int i = (n / 2; i <= n; i++)

Нужно:

cpp
for (int i = (n + 1) / 2; i <= n; i++)

Начинать нужно именно с (n + 1) / 2, а не с n / 2.

Например, если n = 5, то Петя не может иметь 2 кубика, потому что максимум он увидел бы 2 настоящих + 2 отражённых = 4, а видит 5.

Значит минимальное возможное K:

cpp
ceil(n / 2)

В целых числах это:

cpp
(n + 1) / 2

Как работает предпоследний цикл:

cpp
for (int i = (n + 1) / 2; i <= n; i++)

Здесь i — это предполагаемое количество настоящих кубиков K.

Мы проверяем: может ли быть так, что после позиции i стоит отражение части кубиков перед зеркалом.

Пример:

text
n = 6
a = 1 2 3 3 2 1

Проверяем K = 3.

text
1 2 3 | 3 2 1

Правая часть 3 2 1 должна быть зеркальным отражением левой части 1 2 3.

В цикле:

cpp
l2 = i + 1 = 4
r2 = n = 6
len = 3

То есть правая часть:

text
a[4..6] = 3 2 1

Берём слева кусок такой же длины:

cpp
r1 = i = 3
l1 = i - len + 1 = 1

Левая часть:

text
a[1..3] = 1 2 3

Теперь сравниваем:

text
a[1..3] == reverse(a[4..6])
1 2 3  == reverse(3 2 1)
1 2 3  == 1 2 3

Значит K = 3 подходит.

Для K = 6 правая часть пустая, значит Петя мог видеть только настоящие кубики, поэтому 6 тоже подходит.

Сдать решение задачи G-Кубики (2 балла) Ограничен...

Вопрос

Мысль

Ответ

Поделиться этим Q&A