Submission #1105517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105517		_callmelucian	Bliskost (COI23_bliskost)	C++14	44 / 100	401 ms	524288 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int add (int a, int b) {
    assert(0 <= a && a < 26 && 0 <= b && b < 26);
    return a + b - (a + b < 26 ? 0 : 26);
}

int sub (int a, int b) {
    assert(0 <= a && a < 26 && 0 <= b && b < 26);
    return a - b + (a - b >= 0 ? 0 : 26);
}

int mul (int a, int b) {
    assert(0 <= a && a < 26 && 0 <= b && b < 26);
    return 1LL * a * b % 26;
}

struct matrix {
    vector<vector<int>> v;
    int n, m;

    matrix (int n, int m) :
        v(n, vector<int>(m)), n(n), m(m) {}
    matrix (vector<vector<int>> init) :
        v(init), n(v.size()), m(v.size() ? v[0].size() : 0) {}

    vector<int>& operator[] (int x) { return v[x]; }

    matrix operator * (matrix o) {
        assert(m == o.n);
        matrix ans(n, o.m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < o.m; j++)
                for (int k = 0; k < m; k++)
                    ans[i][j] = add(ans[i][j], mul(v[i][k], o[k][j]));
        return ans;
    }
};

const matrix iden2({{1, 0}, {0, 1}});

struct IT {
    vector<matrix> tr;
    IT (int sz) : tr(4 * sz, iden2) {}

    void update (int pos, matrix val, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) return tr[k] = val, void();
        int mid = (l + r) >> 1;
        update(pos, val, 2 * k, l, mid);
        update(pos, val, 2 * k + 1, mid + 1, r);
        tr[k] = tr[2 * k] * tr[2 * k + 1];
    }

    bool valid() { return tr[1][0][1] == 0; }
};

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

    int n, q; cin >> n >> q;
    string s, t; cin >> s >> t;
    s = " " + s, t = " " + t;

    IT tree(n);
    for (int i = 1; i <= n; i++) {
        int val = sub(t[i] - 'a', s[i] - 'a');
        tree.update(i, matrix({{sub(0, 1), val}, {0, 1}}), 1, 1, n);
    }

    cout << (tree.valid() ? "da" : "ne") << "\n";
    for (int i = 0; i < q; i++) {
        int p; char c; cin >> p >> c;
        int val = sub(t[p] - 'a', c - 'a');
        s[p] = c;
        tree.update(p, matrix({{sub(0, 1), val }, {0, 1}}), 1, 1, n);
        cout << (tree.valid() ? "da" : "ne") << "\n";
    }

    return 0;
}

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