1033C - Permutation Game - CodeForces Solution

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

vector<vector<int>> gr;
vector<bool> res;
vector<bool> used;

bool dfs(int u) {
    used[u] = true;
    for (int v : gr[u]) {
        if (!used[v]) {
            dfs(v);
        }
        res[u] = res[u] | !res[v];
    }
    return res[u];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    gr.resize(n);
    res.resize(n);
    used.resize(n);
    for (int i = 0; i < n; ++i) {
        for (int j = i % a[i]; j < n; j += a[i]) {
            if (a[j] > a[i]) {
                gr[i].push_back(j);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            //cout << i;
            dfs(i);
        }
    }
    for (bool val : res) {
        cout << (val ? "A" : "B");
    }
}