Submission #1225170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225170		KALARRY	Permutation (APIO22_perm)	C++20	0 / 100	595 ms	327680 KiB

perm

//chcockolateman

#include<bits/stdc++.h>

using namespace std;

map<long long,long long> calced[130];

long long cost(long long k,long long turn)
{
    if(k==0)
        return 0;
    if(turn > 120)
        return 1e9;
    if(calced[k][turn])
        return calced[k][turn];
    long long pos = 0;
    while((1ll<<(pos+1)) - 1 <= k)
        pos++;
    long long new_k = k - ((1ll<<pos) - 1);
    long long ret = pos + cost(new_k,turn+1);
    if(turn != 1 && k != 1)
    {
        pos = 0;
        while((1ll<<(pos+1)) <= k)
            pos++;
        new_k = k - (1ll<<pos);
        ret = min(ret,pos + cost(new_k,turn+1));
    }
	calced[k][turn] = ret;
    return ret;
}

std::vector<int> construct_permutation(long long k)
{
    k--;
    long long counter = -1;
    vector<long long> seq;
    vector<bool> swapped;
    long long turn = 0;
    while(k)
    {
        turn++;
        long long pos1 = 0;
        while((1ll<<(pos1+1)) - 1 <= k)
            pos1++;
        long long new_k = k - ((1ll<<pos1) - 1);
        long long cost_1 = pos1 + cost(new_k,turn + 1);
        bool chose_first = true;

        long long pos_2 = 0;
        if(turn != 1 && k != 1)
        {
            while((1ll<<(pos_2+1)) <= k)
                pos_2++;
            new_k = k - (1ll<<pos_2);
            long long cost_2 = pos_2 + cost(new_k,turn + 1);
            if(cost_2 < cost_1)
            {
                seq.push_back(pos_2);
                counter += pos_2;
                swapped.push_back(true);
				k -= (1ll<pos_2);
                chose_first = false;
            }
        }
        if(chose_first)
        {
            seq.push_back(pos1);
            counter += pos1;
			k -= ((1ll<<pos1) - 1);
            swapped.push_back(false);
        }
    }

    vector<int> ret;
	for(long long L = 0 ; L < seq.size() ; L++)
    {
        long long last = ret.size() - 1;
        counter = counter - seq[L] + 1;
        for(long long i = 1 ; i <= seq[L] ; i++)
            ret.push_back(counter++);
        counter = counter - seq[L] - 1;
        if(swapped[L])
            swap(ret[last],ret[last+1]);
    }
    return ret;
}

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