Babaza Game

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

#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)(x).size()                                 // signed size: avoids the unsigned .size() wrap bug

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;

#ifdef LOCAL                                                    // compile with -DLOCAL to enable, silent on the judge
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", dbg_out(__VA_ARGS__)
template<class T> void dbg_out(T x) { cerr << x << '\n'; }
template<class T, class... R> void dbg_out(T x, R... r) { cerr << x << ", "; dbg_out(r...); }
#else
#define dbg(...)
#endif

int main() {
    cin.tie(0)->sync_with_stdio(0);                             // never mix with scanf/printf after this

    string s, t; cin >> s >> t; int n = sz(s);
    if (s == t) { cout << s << "\n"; return 0; }

    char F = 'A';
    while (s.find(F) != string::npos || t.find(F) != string::npos) F++;

    // k = 1: all differing positions pairwise non-adjacent
    bool one = true;
    for (int i = 0; i + 1 < n; i++) if (s[i] != t[i] && s[i+1] != t[i+1]) one = false;
    if (one) { cout << s << "\n" << t << "\n"; return 0; }

    // k = 2: pick w[i] from {s[i], t[i]}
    auto cand = [&](int i, int j) { return j == 0 ? s[i] : t[i]; };
    vector<array<int,2>> par(n);
    for (int i = 0; i < n; i++) par[i] = {-2, -2};
    par[0] = {-1, -1};
    for (int i = 0; i + 1 < n; i++) for (int a = 0; a < 2; a++) {
        if (par[i][a] == -2) continue;
        char x = cand(i, a);
        for (int b = 0; b < 2; b++) {
            if (par[i+1][b] != -2) continue;
            char y = cand(i+1, b);
            if (x == y) continue;                                   // row 1 valid
            if (x != s[i] && y != s[i+1]) continue;                 // step 1 conflict
            if (x != t[i] && y != t[i+1]) continue;                 // step 2 conflict
            par[i+1][b] = a;
        }
    }
    int last = -1;
    for (int b = 0; b < 2; b++) if (par[n-1][b] != -2) { last = b; break; }
    if (last >= 0) {
        string w(n, '?');
        for (int i = n - 1; i >= 0; i--) { w[i] = cand(i, last); last = par[i][last]; }
        cout << s << "\n" << w << "\n" << t << "\n"; return 0;
    }

    // k = 3: fallback
    string a = s, b;
    for (int i = 0; i < n; i += 2) a[i] = F;
    b = a;
    for (int i = 1; i < n; i += 2) b[i] = t[i];
    cout << s << "\n" << a << "\n" << b << "\n" << t << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED