Submission #1241004

---

Source Code Expand

#include<algorithm>
#include<vector>
#include<list>
#include<iostream>
#include<utility>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<iterator>
#include<map>
#include<limits>
#include<iomanip>
 
const int INF=2147483647;
 
using namespace std;
 
long long tautCt(long long n){
    if(n<=1) return 0;
    vector<long long> ncr(n+1);
    ncr[0]=1;
    for(int i=1; i<=n; i++){
        ncr[i]=ncr[i-1]*(n+1-i)/i;
        //cout<<ncr[i]<<endl;
    }
    long long ans=0;
    for(int i=2; i<=n; i+=2){
        ans+=ncr[i];
    }
    return ans;
}

long long tautCt2(long long n){
    vector<long long> ncr(n+1);
    ncr[0]=1;
    for(int i=1; i<=n; i++){
        ncr[i]=ncr[i-1]*(n+1-i)/i;
        //cout<<ncr[i]<<endl;
    }
    long long ans=0;
    for(int i=0; i<=n; i++){
        ans+=ncr[i]*ncr[i];
    }
    return ans;
    
}

long long tautCt2(long long m, long long n){
    if(m>n) return tautCt2(n,m);
    
    vector<long long> ncr(n+1), mcr(n+1);
    ncr[0]=1;
    mcr[0]=1;
    for(int i=1; i<=n; i++){
        ncr[i]=ncr[i-1]*(n+1-i)/i;
        //cout<<ncr[i]<<endl;
    }
    for(int i=1; i<=m; i++){
        mcr[i]=mcr[i-1]*(m+1-i)/i;
    }
    
    long long ans=0;
    for(int i=0; i<=m; i++){
        ans+=mcr[i]*ncr[i];
    }
    return ans;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin>>n;
    
    vector<long long> tauts(51), tauts2(51);
    vector<vector<long long>> tauts2b(51,vector<long long>(51,0ll));
    
    
    
    for(int i=0; i<=50; i++){
        tauts[i]=tautCt(i);
        tauts2[i]=tautCt2(i);
    }
    //cout<<tauts[50];
    for(int i=0; i<=50; i++){
        for(int j=0; j<=50; j++){
            tauts2b[i][j]=tautCt2(i,j);
        }
    }
    
    
    //int cur=1;
    
    auto it=lower_bound(tauts.begin(),tauts.end(), n);
    if(*it>n) it--;
    long long cand1=*it;
    int num=(it-tauts.begin());
    n-=*it;
    
    list<int> ans(num,1);
            
    int cur=2;
    
    while(n){
        auto it=ans.begin();
        int i;
        for(i=0; tauts2b[i][num-i]<=n;i++,it++){}
        it--;
        i--;
        
        if(it==ans.begin()) ans.push_front(cur);
        else ans.insert(it,cur);
        
        ans.push_back(cur);
        n-=tauts2b[i][num-i];
        cur++;
    }
    
    
    /*
    while(n){
        auto it=lower_bound(tauts.begin(),tauts.end(), n);
        if(*it>n) it--;
        long long cand1=*it;
        int num=(it-tauts.begin());
        
        long long cand2=0;
        int num1=100, num2=100;
        for(int i=1; tauts[i]<n; i++){
            for(int j=1; j<=i; j++){
                long long tot=tauts[i+j]+tauts2b[i][j];
                if(tot<=n && tot>cand2 || tot==cand2 && i+j<num1+num2){
                    cand2=tot;
                    num1=j;
                    num2=i;
                }
            }
        }
        
        
        
        int pos=0;
        while(n>tauts[2*pos]+tauts2[pos]){
            pos++;
        }
        if(n!=tauts[2*pos]+tauts2[pos]) pos--;
        cand2=tauts[2*pos]+tauts2[pos];
        
        
        if(cand2>cand1 && num1+num2+1<=num){
            n-=cand2;
            for(int i=0; i<num1; i++){
                ans.push_back(cur);
            }
            ans.push_back(cur+1);
            for(int i=0; i<num2; i++){
                ans.push_back(cur);
            }
            ans.push_back(cur+1);
            cur+=2;
        }
        
        
        else{
            n-=*it;
            for(int i=0; i<num; i++){
                ans.push_back(cur);
            }
            cur++;
        }
        cout<<n<<endl;
    }
    */
    
    cout<<ans.size()<<endl;
    for(int i:ans){
        cout<<i<<" ";
    }
    
    
    
    
    
    
    
    
    return 0;
}

Submission Info

Judge Result