oj.uz

Submission #953674

# Submission time Handle Problem Language Result Execution time Memory
953674 2024-03-26T12:28:09 Z De3b0o Permutation (APIO22_perm) C++17
91.3333 / 100
 103 ms 716 KB 
#include "perm.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
//#define lc (2*n)
//#define rc (2*n+1)

using namespace std;


ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y&1)
        return z*z*x;
    else
        return z*z;
}

std::vector<int> construct_permutation(long long k)
{
    vector<ll> v;
    k--;
    ll p = 0;
    while(k>0)
    {
        ll y = 0;
        ll x = k;
        while(x)
        {
            x/=2;
            y++;
        }
        ll e = fp(2,min(y,p));
        if(e>k)
        {
            e=fp(2,min(y,p)-1);
            k-=e;
            v.pb(min(y,p)-1);
        }
        else
        {
            k-=e;
            v.pb(min(y,p));
        }
        p++;
    }
    ll n = v.size();
    vector<int> ans(n,0);
    map<ll,ll> mp;
    for(int i = n-1 ; i>=0 ; i--)
    {
        ll y;
        for(int j = 0 ; n>j ; j++)
        {
            if(mp[j]==1)
                continue;
            ll x = j;
            for(auto it : mp)
            {
                if(it.S==1)
                {
                    if(it.F<j)
                        x--;
                }
            }
            if(x==v[i])
            {
                y=j;
                break;
            }
        }
        ans[i]=y;
        mp[y]=1;
    }
    return ans;
}

Compilation message

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:88:15: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |         ans[i]=y;

Subtask #1
10.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 424 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 6 ms 444 KB Output is correct
5 Partially correct 39 ms 468 KB Partially correct
6 Correct 25 ms 464 KB Output is correct
7 Correct 63 ms 456 KB Output is correct
8 Partially correct 85 ms 452 KB Partially correct
9 Correct 46 ms 600 KB Output is correct
10 Partially correct 103 ms 716 KB Partially correct
11 Partially correct 76 ms 436 KB Partially correct
12 Partially correct 65 ms 452 KB Partially correct
13 Partially correct 85 ms 448 KB Partially correct