Submission #580189

#	Time	Username	Problem	Language	Result	Execution time	Memory
580189		MohamedAliSaidane	Permutation (APIO22_perm)	C++17	100 / 100	37 ms	356 KiB

perm

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef long double ld;
        /// #define int ll
        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second



        int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}



        vi construct_permutation(ll k)
        {
            //cout << k << '\n';
            if(k == 1)
                return {};
            if(k == 2)
                return {0};

            for(ll i = 2ll; i <= 1e4 && i * i <= k; i ++)
            {
                if(k%i == 0)
                {
                    vi v = construct_permutation(i);
                    vi u = construct_permutation(k/i);
                    int sz = v.size();
                    for(auto e: u)
                        v.pb(e + sz);
                    return v;
                }
            }
            vi v = construct_permutation(k/2ll);
            int sz= v.size();
            v.pb(sz);
            vi ans;
            if(k & 1)
                ans.pb(v.size());
            for(auto e: v)
                ans.pb(e);
            return ans;
        }
        /*
        int32_t main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            int tt; cin >> tt;
            while(tt --)
            {
                ll k; cin >> k;
                vi ans = construct_permutation(k);
                cout << ans.size() << '\n';
                for(auto e: ans)
                    cout << e << ' ';
                cout << '\n';
            }
        }
        */

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90