Để thoả mãn cả ~3~ điều kiện thì ta có một cách dựng ~2~ số ~a~, ~b~ đơn giản như sau:

Xét một đoạn các bit ~1~ liên tiếp trong ~c~, gọi đoạn đó là đoạn ~[l, r]~. Vì ~2^{r+1} - 2^l = 2^l + 2^{l+1} + ... + 2^r~, nên ta chỉ cần thay đổi bit ~r + 1~ của ~a~ và bit ~l~ của ~b~ thành ~1~ ta sẽ thoả mãn điều kiện của đề bài.

Độ phức tạp: ~O(n)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int LOG = 22; 
const int MAX = 2e5+5;
const int MOD = 1e9+7;
const int SQRT = 400;
const ll INF = 2e9;
const ll lon = 1e18;

int n;
string c, a, b;
vector<pii> segment;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> c;
    c = '0'+c;
    fo(i, 1, n-1) {
        if(c[i] == '0') continue;
        if(c[i-1] == '0') segment.pb(mk(i, i-1));
        segment.back().se++;
    }

    a.assign(n, '0');
    b.assign(n, '0');
    foa(elem, segment) {
        a[elem.fi-1] = '1';
        b[elem.se] = '1';
    } 
    cout << a << "\n" << b;
}