Submission #1083900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083900		alexander707070	Permutation (APIO22_perm)	C++17	100 / 100	1 ms	440 KiB

perm

#include<bits/stdc++.h>

#define MAXN 200007
using namespace std;

int num;
deque<int> perm;
vector<int> ans,w;
bool fr;

int after[120];
vector<int> incr,bonus,decr;

void mult(){
    incr.push_back(num);
    num++;
}

void add1(){
    bonus.push_back(num);
    num++;
}

void add3(){
    after[num]=bonus[bonus.size()-2];
    decr.push_back(num);
    num++;
}

void reset(){
    fr=false; num=0;
    decr.clear(); incr.clear(); 
    bonus.clear(); ans.clear();
}

int bit[70];

vector<int> construct_permutation(long long k){
    reset();

    for(int i=62;i>=0;i--){
        if(((1LL<<i)&k)>0)bit[i]=1;
        else bit[i]=0;
    }

    for(int i=62;i>=0;i--){
        if(bit[i]==1){
            if(!fr)fr=true;
            else{
                if(i>0 and bit[i-1]==1 and bonus.size()>=2){
                    mult(); mult();
                    add3(); i--;
                }else{
                    mult(); add1();
                }
            }
        }else{
            if(!fr)continue;
            mult();
        }
    }

    for(int i=bonus.size()-1;i>=0;i--){
        ans.push_back(bonus[i]);

        while(!decr.empty() and after[decr.back()]==bonus[i]){
            ans.push_back(decr.back());
            decr.pop_back();
        }
    }

    for(int i=0;i<incr.size();i++){
        ans.push_back(incr[i]);
    }

    return ans;
}

/*int main(){
    w=construct_permutation(91);

    for(int i:w)cout<<i<<" ";

    w=construct_permutation(91);

    for(int i:w)cout<<i<<" ";
}*/

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<incr.size();i++){
      |                 ~^~~~~~~~~~~~

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