Babaza Game

input/code.cpp: In function 'bool two(std::string&, std::string&, std::string&)':
input/code.cpp:58:14: warning: unused variable 'ch' [-Wunused-variable]
   58 |         char ch = 'A' + c;
      |              ^~

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define fill(arr,val) memset(arr,val,sizeof(arr))
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define dq deque<int>
#define nend '\n'
using namespace std;
const ll hashi=2e9+11;
ll add(ll a, ll b) {
    return (a+b)%hashi;
}
ll sub(ll a, ll b) {
    return ((a-b)%hashi+hashi)%hashi;
}
ll mul(ll a, ll b) {
    return (a*b)%hashi;
}

const ll inf=1e18;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};


// Can we transform a -> b in exactly one move
bool one(string &a, string &b) {
    int n = a.size();

    for(int i = 0; i + 1 < n; i++) {
        if(a[i] != b[i] && a[i+1] != b[i+1])
            return false;
    }

    return true;
}


bool two(string &a,string &b, string &x) {
    int n = a.size();

    bool dp[11][26];
    int par[11][26];

    fill(dp, 0);
    fill(par, -1);

    for(int c = 0; c < 26; c++) {
        char ch = 'A' + c;
        dp[0][c] = 1;
    }

    for(int i = 1; i < n; i++) {
        for(int c = 0; c < 26; c++) {
            char ch = 'A' + c;

            for(int p = 0; p < 26; p++) {
                if(!dp[i-1][p]) continue;

                char prev = 'A' + p;

                if(prev == ch) continue;
                bool left = (a[i-1] != prev);
                bool now = (a[i] != ch);

                if(left && now)
                    continue;
                bool left2 = (prev != b[i-1]);
                bool now2 = (ch != b[i]);

                if(left2 && now2)
                    continue;

                dp[i][c] = true;
                par[i][c] = p;
                break;
            }
        }
    }

    int last = -1;

    for(int c = 0; c < 26; c++) {
        if(dp[n-1][c]) {
            last = c;
            break;
        }
    }

    if(last == -1)
        return false;

    x.resize(n);

    for(int i = n-1; i >= 0; i--) {
        x[i] = char('A' + last);

        if(i > 0)
            last = par[i][last];
    }
    if(x == a || x == b)
        return false;

    return true;
}


int main() {
    //freopen("file.inp","r",stdin);
    //freopen("file.out","w",stdout);
    fast;

    string a, b;
    cin >> a >> b;

    int n = a.size();
    if(a == b) {
        cout << a << nend;
        return 0;
    }
    if(one(a, b)) {
        cout << a << nend << b;
        return 0;
    }
    string mid;

    if(two(a, b, mid)) {
        cout << a << nend << mid << nend << b;
        return 0;
    }

    string x = a;

    for(int i = 0; i < n; i += 2) {
        bool used[26] = {};
        if(i-1 >= 0) {
            used[a[i-1] - 'A'] = 1;
            used[b[i-1] - 'A'] = 1;
        }

        if(i + 1 < n) {
            used[a[i+1] - 'A'] = 1;
            used[b[i+1] - 'A'] = 1;
        }

        for(int c = 0; c < 26; c++) {
            if(!used[c]) {
                x[i] = char('A' + c);
                break;
            }
        }
    }

    string y = x;

    for(int i = 1; i < n; i += 2)
        y[i] = b[i];

    string z = y;
    for(int i = 0; i < n; i += 2)
        z[i] = b[i];

    cout << a << nend << x << nend << y;

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

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