oj.uz

Submission #983509

# Submission time Handle Problem Language Result Execution time Memory
983509 2024-05-15T15:20:45 Z Faisal_Saqib Permutation (APIO22_perm) C++17
91.3333 / 100
 14 ms 476 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=1e4;
    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 1 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct

Subtask #2
81.333333333 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Partially correct 9 ms 348 KB Partially correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 11 ms 348 KB Output is correct
8 Partially correct 13 ms 452 KB Partially correct
9 Correct 12 ms 348 KB Output is correct
10 Partially correct 13 ms 468 KB Partially correct
11 Partially correct 12 ms 476 KB Partially correct
12 Correct 14 ms 468 KB Output is correct
13 Correct 13 ms 348 KB Output is correct