1517C - Fillomino 2 - CodeForces Solution

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

#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#define int long long
#define float long double
#define pii pair<int, int>
#define pis pair<int, string>
#define eb emplace_back
#define pb push_back
#define pf push_front
#define F first
#define S second
#define mp make_pair
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vpii vector<pii>
#define all(n) (n).begin(), (n).end()
template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
    for (auto &i : a)
        cin >> i;
    return in;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &a)
{
    for (auto &i : a)
        cout << i << " ";
    return out;
}

/*
Helper Function
*/

// ------------ Binary & of a range of numbers in O(logN) time -----------------------
// https://www.geeksforgeeks.org/bitwise-and-or-of-a-range/
int msbPos(int n)
{
    int msb_p = -1;
    while (n)
    {
        n = n >> 1;
        msb_p++;
    }
    return msb_p;
}

int andOperator(int x, int y)
{
    int res = 0;

    while (x && y)
    {
        // Find positions of MSB in x and y
        int msb_p1 = msbPos(x);
        int msb_p2 = msbPos(y);

        // If positions are not same,break
        if (msb_p1 != msb_p2)
            break;

        // Add 2^msb_p1 to result
        int msb_val = (1LL << msb_p1);
        res = res + msb_val;

        // subtract 2^msb_p1 from x and y.
        x = x - msb_val;
        y = y - msb_val;
    }
    return res;
}

// ---------------------------- Prime Numbers till N -----------------------------
vector<int> primes;
vector<bool> sieve(int n)
{
    vector<bool> prime(n + 1, true);
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            primes.pb(p);
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    return prime;
}

// ----------------------------- Segment Tree --------------------------------------
class SGMTree
{
    vector<int> minSeg, maxSeg;

public:
    SGMTree(int n)
    {
        minSeg.resize(4 * n + 1);
        maxSeg.resize(4 * n + 1);
    }
    void buildMin(int ind, int low, int high, vector<int> &arr)
    {
        if (low == high)
        {
            minSeg[ind] = arr[low];
            return;
        }
        int mid = (low + high) / 2;

        buildMin(2 * ind + 1, low, mid, arr);
        buildMin(2 * ind + 2, mid + 1, high, arr);

        minSeg[ind] = min(minSeg[2 * ind + 1], minSeg[2 * ind + 2]);
    }
    void buildMax(int ind, int low, int high, vector<int> &arr)
    {
        if (low == high)
        {
            maxSeg[ind] = arr[low];
            return;
        }
        int mid = (low + high) / 2;

        buildMax(2 * ind + 1, low, mid, arr);
        buildMax(2 * ind + 2, mid + 1, high, arr);

        maxSeg[ind] = max(maxSeg[2 * ind + 1], maxSeg[2 * ind + 2]);
    }
    int queryMin(int ind, int low, int high, int l, int r)
    {
        if (r < low || high < l)
            return INT_MAX;
        if (low >= l && high <= r)
            return minSeg[ind];
        int mid = (low + high) >> 1;

        int left = queryMin(2 * ind + 1, low, mid, l, r);
        int right = queryMin(2 * ind + 2, mid + 1, high, l, r);

        return min(left, right);
    }
    int queryMax(int ind, int low, int high, int l, int r)
    {
        if (r < low || high < l)
            return INT_MIN;
        if (low >= l && high <= r)
            return maxSeg[ind];
        int mid = (low + high) >> 1;

        int left = queryMax(2 * ind + 1, low, mid, l, r);
        int right = queryMax(2 * ind + 2, mid + 1, high, l, r);

        return max(left, right);
    }
};

// Modular Arithmetic
int MOD = 1e9 + 7;
int mod(int x, int M) { return ((x % M + M) % M); }
int add(int a, int b, int M) { return mod(mod(a, M) + mod(b, M), M); }
int mul(int a, int b, int M) { return mod(mod(a, M) * mod(b, M), M); }

/*

------------------------------------------------------


MAIN CODE


-----------------------------------------------------


*/

void solve();

int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << "\n";
    }
    return 0;
}

void dfs(int cx, int cy, vector<vector<int>> &ans, vector<int> &a, int n, int val, int &cnt)
{
    if (cx < 0 || cx >= n || cy < 0 || cy >= n || cy > cx || ans[cx][cy] != 0)
    {
        return;
    }
    if (cnt == val)
        return;
    ans[cx][cy] = val;
    cnt += 1;

    dfs(cx, cy - 1, ans, a, n, val, cnt);
    dfs(cx + 1, cy, ans, a, n, val, cnt);
    dfs(cx, cy + 1, ans, a, n, val, cnt);
    dfs(cx - 1, cy, ans, a, n, val, cnt);
}
void solve()
{
    int n;
    cin >> n;
    vi a(n);
    cin >> a;

    vector<vector<int>> ans(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        dfs(i, i, ans, a, n, a[i], cnt);
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
            cout << ans[i][j] << " ";
        cout << "\n";
    }
}