Submission #39912600

---

Source Code Expand

#include <bits/stdc++.h>
//#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;

//#define int long long
//#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    a[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int j = 1;
        vector<int> divs;
        for (int k = 1; k * k <= i; k++)
        {
            if (i % k == 0)
            {
                divs.push_back(k);
                if (i / k != k) divs.push_back(i / k);
            }
        }
        sort(divs.begin(), divs.end(), [&](int p1, int p2) {return a[p1] < a[p2];});
        for (auto& x : divs)
        {
            if (a[x] == j)
                j++;
        }
        a[i] = j;
    }
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
//Я ЛЮБЛЮ ИГОРЯ МОРОЗА
/*
3 3
1 2 0
2 3 1
1 3 0
*/

/*
2 1 3
1 1 1 4
1 1 2 6
1 3

1 5
1 7
*/

/*
1 1 1
100000000 1 1 1
1 1
*/

/*
4 4
1 2 1 3
1 1
1 2
1 3
1 4
*/

Submission Info

Judge Result