Submission #1311477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311477		og_matveychick1	Nice sequence (IZhO18_sequence)	C++20	15 / 100	58 ms	6916 KiB

sequence

#include <iostream>
#include <vector>
#include <numeric>
#include <queue>

using namespace std;

// Функция для нахождения НОД
long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

void solve() {
    long long N, M;
    if (!(cin >> N >> M)) return;

    long long g = gcd(N, M);
    // 1. Считаем максимальную длину
    long long K = N + M - g - 1;

    cout << K << endl;
    if (K == 0) {
        cout << endl;
        return;
    }

    // Массив префиксных сумм
    vector<long long> S(K + 1, 0);
    vector<bool> visited(K + 1, false);

    // 2. и 3. Обходим граф для заполнения S
    // Ребра: i -> i+M (вес +2), i -> i+N (вес -2)
    // Используем +/- 2, чтобы контролировать четность и избежать нулей в ответе

    for (int r = 0; r < g; ++r) {
        // r - стартовая точка для каждой компоненты связности (остаток от деления на g)
        // Если K маленькое, r может выходить за пределы, проверяем это
        if (r > K) continue;
        if (visited[r]) continue;

        queue<int> q;
        q.push(r);
        visited[r] = true;

        // Хитрость с четностью: S[i] и S[i-1] будут иметь разную четность,
        // так как они принадлежат разным компонентам (или сдвинуты на 1).
        // S[r] = 0 для четных r, 1 для нечетных.
        S[r] = (r % 2);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            // Переход вперед на M (+2)
            if (u + M <= K && !visited[u + M]) {
                visited[u + M] = true;
                S[u + M] = S[u] + 1;
                q.push(u + M);
            }
            // Переход вперед на N (-2)
            if (u + N <= K && !visited[u + N]) {
                visited[u + N] = true;
                S[u + N] = S[u] - 1;
                q.push(u + N);
            }
            // Переход назад на M (-2)
            if (u - M >= 0 && !visited[u - M]) {
                visited[u - M] = true;
                S[u - M] = S[u] - 1; // обратная операция к +2
                q.push(u - M);
            }
            // Переход назад на N (+2)
            if (u - N >= 0 && !visited[u - N]) {
                visited[u - N] = true;
                S[u - N] = S[u] + 1; // обратная операция к -2
                q.push(u - N);
            }
        }
    }

    // 4. Восстанавливаем последовательность
    for (int i = 1; i <= K; ++i) {
        cout << (S[i] - S[i - 1]) << (i == K ? "" : " ");
    }
    cout << endl;
}

int main() {
    // Ускорение ввода-вывода
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 15 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24