sequencias.cpp

#include<bits/stdc++.h>
using namespace std;

vector<int> dp[1000010];

int tam[1000010];

vector<int> solve(int num){
    if(!dp[num].empty())return dp[num];
    vector<int> resp;

    vector<int> divisores;

    int aux=num;

    for(int i=2; i*i<=aux; i++){
        if(aux%i==0){
            while(aux%i==0){
                if(i==2){
                    if(aux%4==0){
                        divisores.push_back(4);
                        aux/=4;
                    }
                    else{
                        divisores.push_back(2);
                        aux/=2;
                    }
                }
                else{
                    divisores.push_back(i);
                    aux/=i;
                }
            }
        }
    }

    if(divisores.empty()){
        vector<int> aux1=solve(num-1), aux2=solve(num-2);
        if(2*tam[num-2]+aux2.size()<tam[num-1]+aux1.size()){
            for(int i=1; i<=tam[num-2]; i++){
                resp.push_back(aux2.size()+tam[num-2]);
            }
            for(int i=1; i<=tam[num-2]; i++){
                resp.push_back(aux2.size()-tam[num-2]);
            }

            for(auto x:aux2)
                resp.push_back(x-2*tam[num-2]);

            tam[num]=tam[num-2];

            return dp[num]=resp;
        }
        else if(2*tam[num-2]+aux2.size()==tam[num-1]+aux1.size()){
            if(tam[num-2]<tam[num-1]){
                for(int i=1; i<=tam[num-2]; i++){
                    resp.push_back(aux2.size()+tam[num-2]);
                }
                for(int i=1; i<=tam[num-2]; i++){
                    resp.push_back(aux2.size()-tam[num-2]);
                }

                for(auto x:aux2)
                    resp.push_back(x-2*tam[num-2]);

                tam[num]=tam[num-2];

                return dp[num]=resp;
            }
        }

        for(int i=1; i<=tam[num-1]; i++){
            resp.push_back(aux1.size());
        }

        for(auto x:aux1)
            resp.push_back(x-tam[num-1]);

        tam[num]=tam[num-1];
        return dp[num]=resp;
    }

    if(aux!=1)divisores.push_back(aux);

    for(auto x:divisores){
        vector<int> aux1=solve(x);
        tam[num]+=tam[x];
        for(auto y:aux1)
            resp.push_back(y);
    }

    return dp[num]=resp;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int l;
    cin >> l;

    dp[1]={0};
    dp[2]={1, -1};
    dp[3]={2, 0, -2};
    dp[4]={3, 1, -1, -3};
    dp[5]={4, 2, 0, -2, -4};
    dp[6]={1, -1, 2, 0, -2};
    dp[7]={6, 4, 2, 0, -2, -4, -6};
    dp[8]={1, -1, 3, 1, -1, -3};
    dp[46]={11, 11, 11, -1, -3, -5, -1, -3, -5, 1, -1, -3, -5, -7};
    tam[1]=tam[2]=tam[3]=tam[4]=tam[5]=1;
    tam[6]=2;
    tam[7]=1;
    tam[8]=2;
    tam[46]=3;

    vector<int> resp=solve(l);

    cout << resp.size() << '\n';

    for(int i=1; i<=resp.size(); i++){
        cout << i+resp[i-1] << " ";
    }
    cout << '\n';

    return 0;
}