Submission #1286679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286679		papaulo	Permutation (APIO22_perm)	C++20	100 / 100	510 ms	28632 KiB

perm

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

using ll = long long;

#define MAXV (1<<16)
vector<int> primos;
vector<int> dp[MAXV];
map<ll, vector<int>> pans;
int initted=0;

int count_increasing_b(const vector<int>& v) {
  vector<int> dp(v.size() + 1, 0);
  dp[0] = 1;
  for (int x : v)
  {
  	for (int i = 0; i <= x; i++)
  	{
  		dp[x+1] += dp[i];
  	}
  }
  int result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
  	result += dp[i];
  }
  return result;
}

int isdiv(ll v) {
    for(auto i : primos) {
        while(v%i==0) v/=i;
    }
    return v==1;
}

vector<int> add(vector<int> a, vector<int> b) {
	vector<int> ans;
	for(auto v : a) ans.push_back(v+(int)b.size());
	for(auto v : b) ans.push_back(v);
	return ans;
}

vector<int> multiply(vector<int> a, vector<int> b) {
	vector<int> ans;
	for(auto v : a) ans.push_back(v);
	for(auto v : b) ans.push_back(v+(int)a.size());
	return ans;
}

vector<int> getdp(ll v) {
	ll ov=v;
	if(pans.find(v)!=pans.end()) return pans[v];
    vector<int> ans(100);
	ll diff=0;
    while((int)ans.size()>90) {
        while(!isdiv(v)) {
            --v;
            ++diff;
        }
        ans=vector<int>();
        ll prod=1;
		ll val=v;
        for(auto i : primos) {
            while(val%i==0) {
                val/=i;
                prod*=i;
                if(prod>=MAXV) {
                    prod/=i;
                    ans=multiply(ans, dp[prod]);
                    prod=i;
                }
            }
        }
        ans=multiply(ans, dp[prod]);
		ans=add(ans, dp[diff+1]);
		++diff;
		--v;
		//cout << v << " " << diff << " " << ans.size() << endl;
    }
	pans[ov]=ans;
    return ans;
}

int primo(int v) {
    for(int i=2;i*i<=v;i++) if(v%i==0) return 0;
    return 1;
}

void init() {
	if(initted) return;
	initted=1;
	for(int i=0;i<MAXV;i++) dp[i]=vector<int>(100);
    for(int n=0;n<=9;n++) {
        vector<int> vec;
        for(int i=0;i<n;i++) vec.push_back(i);
        do {
            int ct=count_increasing_b(vec);
            if(ct>MAXV) continue;
            if(n<(int)dp[ct].size()) dp[ct]=vec;
        } while(next_permutation(vec.begin(), vec.end()));
    }
    for(int k=0;k<5;k++) {
        for(int i=2;i<MAXV;i++) {
            int l=min(i, 512);
            for(int j=1;j<l;j++) {
                if((int)dp[j].size()+(int)dp[i-j+1].size()<(int)dp[i].size()) dp[i]=add(dp[j], dp[i-j+1]);
            }
        }
        for(int i=2;i<MAXV;i++) {
            for(int j=2, k=2*i;j<=i&&k<MAXV;j++,k+=i) {
                if((int)dp[i].size()+(int)dp[j].size()<(int)dp[k].size()) dp[k]=multiply(dp[i], dp[j]);
            }
        }
    }
    for(int i=2;i<MAXV;i++) {
        if(primo(i)) primos.push_back(i);
    }
}

vector<int> construct_permutation(long long k) {
	init();
	return getdp(k);
}

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