oj.uz

Submission #580189

# Submission time Handle Problem Language Result Execution time Memory
580189 2022-06-20T17:17:15 Z MohamedAliSaidane Permutation (APIO22_perm) C++17
100 / 100
 37 ms 356 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 10 ms 340 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 30 ms 352 KB Output is correct
9 Correct 26 ms 356 KB Output is correct
10 Correct 29 ms 332 KB Output is correct
11 Correct 37 ms 352 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 12 ms 332 KB Output is correct