oj.uz

Submission #983505

# Submission time Handle Problem Language Result Execution time Memory
983505 2024-05-15T15:19:19 Z Faisal_Saqib Permutation (APIO22_perm) C++17
97 / 100
 842 ms 700 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vll vector<int>
vector<int> cp(ll k)// O(lg n)
{
    vector<int> ans;
    ll n_req=0;
    ll hb=-1;
    for(int j=59;j>=0;j--)
    {
        ll pw=(1ll<<j);
        if(k&pw)
        {
            if(hb==-1)
            {
                n_req+=j;
                hb=j;
            }
            else
                n_req++;
        }
    }
    ll last=n_req-1;
    int first=0;
    // cout<<last<<endl;
    for(int l=0;l<60 and l<hb;l++)
    {
        if(k&(1ll<<l))
        {
            ans.push_back(first);
            first++;
        }
        if(first<=last)
        {
            ans.push_back(last);
            last--;
        }
    }
    reverse(begin(ans),end(ans));
    return ans;
}
ll task(ll n) // O(lg n)
{
    ll cp=0;
    for(int bit=59;bit>=0;bit--)
    {
        if(n&(1ll<<bit))
        {
            cp+=bit;
            n^=(1ll<<bit);
            break;
        }
    }
    while(n)
    {
        cp++;
        n-=(n&-n);
    }
    return cp;
}
vector<int> construct_permutation(ll k)
{
    // vector<int> ans=cp(k);
    ll mx=task(k);
    ll a=-1;
    ll b=k;
    // if(mx<90)
    // {
    //     return ans;
    // }
    ll SQ=8e5;
    for(ll d=1;d<=SQ;d++)
    {
        if(k%d==0)
        {
            ll f=task(d);
            ll s=task(k/d);
            if((f+s)<mx)
            {
                mx=f+s;
                a=d;
                b=k/d;
            }
        }
    }
    if(a==-1)
    {
        return cp(k);
    }
    else{
        vll ap=cp(a);
        vll bp=cp(b);
        ll nm=ap.size();
        for(auto i:bp)
            ap.pb(i+nm);
        return ap;
    }
    return {};
}
// int main()
// {
//     int n;
//     cin>>n;
//    auto tp= construct_permutation(n);
//    for(auto k:tp)
//    {
//     cout<<k<<' ';
//    }
//    cout<<endl;
// }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 305 ms 428 KB Output is correct

Subtask #2
87.000000003 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 305 ms 428 KB Output is correct
3 Correct 343 ms 412 KB Output is correct
4 Correct 373 ms 592 KB Output is correct
5 Partially correct 539 ms 680 KB Partially correct
6 Correct 582 ms 600 KB Output is correct
7 Correct 703 ms 416 KB Output is correct
8 Partially correct 823 ms 592 KB Partially correct
9 Correct 842 ms 424 KB Output is correct
10 Partially correct 841 ms 688 KB Partially correct
11 Partially correct 802 ms 684 KB Partially correct
12 Correct 759 ms 700 KB Output is correct
13 Correct 817 ms 688 KB Output is correct