Submission #983398

#	Time	Username	Problem	Language	Result	Execution time	Memory
983398		riariti	Bliskost (COI23_bliskost)	C++17	100 / 100	167 ms	16568 KiB

Main

#include <bits/stdc++.h>

namespace MX {

constexpr int A = 26;

}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // consider string as a number in modulo 26
    //
    // call string a, b the 2 strings you need to check if close (after the op)
    // clarification in first example (abc is string a, ced is string b)
    //
    // doing op (adding 11 to the pair) on string b is equivalent to subtracting
    // string a, so we can keep string b constant
    //
    // we know how much to add on each position, consider an array that
    // represents value needed to add to char in string a to get b start with 0,
    // and construct bi - ai via the +1 on consec operation (and its reverse as
    // mentioned above) for which array is it possible to build such an array so
    // when added to ai you get bi
    //
    // lets call this array above c, ci = bi - ai for all i
    //
    // check selected problems: https://oj.uz/problem/view/COI23_bliskost for
    // diagram
    //
    // so basically first operation is c_0, c_1 - c_0, c2 - c1 + c0 ... c_n-2 -
    // c_n-3 + ... +/- c0 should be equal to c_(n - 1) ofc in modulo 26
    //
    // c_(n - 1) + c_(n - 3) + ... = c_(n - 2) + c_(n - 4) + ...
    //
    // so odd positions sum should be equal to even positions sum (ofc in mod
    // 26) whcih we can keep track trivially

    int N, Q;
    std::cin >> N >> Q;
    std::string A;
    std::cin >> A;
    std::string B;
    std::cin >> B;

    int odd = 0, eve = 0;
    for (int i = 0; i < N; i++) {
        (i % 2 ? odd : eve) += (B[i] - A[i] + MX::A) % MX::A;
        odd += MX::A;
        odd %= MX::A;
        eve += MX::A;
        eve %= MX::A;
    }

    std::cout << (odd == eve ? "da" : "ne") << "\n";

    for (int q = 0; q < Q; q++) {
        int p;
        char c;
        std::cin >> p >> c;
        p--;

        (p % 2 ? odd : eve) -= (B[p] - A[p]);
        A[p] = c;
        (p % 2 ? odd : eve) += (B[p] - A[p]);
        odd += MX::A;
        odd %= MX::A;
        eve += MX::A;
        eve %= MX::A;

        std::cout << (odd == eve ? "da" : "ne") << "\n";
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 17 / 17
• Subtask 6: 43 / 43