Stone Game Solution || Codechef Starters - 26

     

Stone Game Solution 

Codechef Starters - 26

Problem Code : STNGAME

Problem Link : https://www.codechef.com/START26B/problems/STNGAME

Solution :

#include <bits/stdc++.h>

#define ll long long int

#define ull unsigned long long int

using namespace std;

void solve()

{

    ll n;

    cin >> n;

    string a, b;

    cin >> a;

    cin >> b;

    vector<char> ans(2 * n);

    sort(a.begin(), a.end());

    sort(b.rbegin(), b.rend());

    ll ansstart = 0, ansend = (2 * n) - 1;

    ll astart = 0, aend = n - 1;

    ll bstart = 0, bend = n - 1;

    for (ll i = 0; i < 2 * n; i++)

    {

        if (i % 2 == 0)

        {

            if (bstart <= bend && a[astart] >= b[bstart])

            {

                ans[ansend] = a[aend];

                ansend--;

                aend--;

            }

            else

            {

                ans[ansstart] = a[astart];

                astart++;

                ansstart++;

            }

        }

        else

        {

            if (astart <= aend && a[astart] < b[bstart])

            {

                ans[ansstart] = b[bstart];

                ansstart++;

                bstart++;

            }

            else

            {

                ans[ansend] = b[bend];

                ansend--;

                bend--;

            }

        }

    }

    for (ll i = 0; i < 2 * n; i++)

    {

        cout << ans[i];

    }

    cout << "\n";

}

int main()

{

    ll t;

    cin >> t;

    while (t--)

    {

        solve();

    }

}