990D - Graph And Its Complement

Editorial.

Time complexity: $O(n^2)$

Memory complexity: $O(n^2)$

Click to show code.


using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
pair<bool, vector<vi>> solve(int n, int a, int b)
{
    if (min(a, b) != 1 or (a == b and (n == 2 or n == 3)))
        return {false, {}};
    vector<vi> ans(n, vi(n, 0));
    bool rev = false;
    if (a < b)
    {
        rev = true;
        swap(a, b);
    }
    for (int i = 0; i < n - a; ++i)
        ans[i][i + 1] = ans[i + 1][i] = 1;
    if (rev)
    {
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (i == j)
                    continue;
                ans[i][j] = 1 - ans[i][j];
            }
        }
    }
    return {true, ans};
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, a, b;
    cin >> n >> a >> b;
    if (auto [flag, mat] = solve(n, a, b); flag)
    {
        cout << "YES" << endl;
        for (auto row : mat)
        {
            for (auto x : row)
                cout << x;
            cout << endl;
        }
    }
    else
        cout << "NO" << endl;
    return 0;
}