Submission #1312284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312284		danglayloi1	Permutation (APIO22_perm)	C++20	91.33 / 100	73 ms	576 KiB

perm

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=105;
ll add(ll a, ll b)
{
    a+=b;
    if(a>=2e18) return 2e18;
    return a;
}
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int get(int l, int r)
{
    return l+mt()*mt()%(r-l+1);
}
ll dp[100];
ll cal(vector<int> ve)
{
    ll sum=1;
    for(int i = 0; i < ve.size(); i++)
        dp[i]=0;
    for(int i = 0; i < ve.size(); i++)
    {
        dp[ve[i]]=1;
        for(int j = 0; j < ve[i]; j++)
            dp[ve[i]]=add(dp[ve[i]], dp[j]);
        sum=add(sum, dp[ve[i]]);
    }
    return sum;
}
vector<int> construct_permutation(ll k)
{
    // if(k<=90)
    // {
    //     vector<int> res;
    //     res.clear();
    //     for(int i = k-2; i >= 0; i--)
    //         res.emplace_back(i);
    //     return res;
    // }
    int lim=120;
    ll cur=1;
    vector<int> ve, sus;
    for(int te = 1; te <= 100; te++)
    {
        cur=2;
        ve.clear();
        ve.emplace_back(0);
        while(cur<k && (int)ve.size()<lim)
        {
            cur=cal(ve);
            ll pre=1;
            pair<ll, int> best={cur+1, 0};
            for(int i = 0; i < ve.size(); i++)
            {
                pre=add(pre, dp[ve[i]]);
                ll nxt=add(cur, pre);
                if(nxt<=k)
                {
                    if(best.fi<nxt)
                        best={nxt, i+1};
                }
            }
            ve.insert(ve.begin()+best.se, ve.size());
            cur=cal(ve);
        }
        // cerr<<cur<<' ';
        // for(int x:ve) cerr<<x<<' ';
        // cerr<<'\n';
        if(cur==k) return ve;
    }
    assert(0);
}
// int main()
// {
//     vector<int> ve=construct_permutation(1000000000000000000);
//     cout<<cal(ve)<<'\n';
//     for(int x:ve) cout<<x<<' ';
//     // for(int k = 2; k <= 90; k++)
//     // {
//     //     vector<int> ve=construct_permutation(k);
//     //     if(cal(ve)!=k) return cout<<k, 0;
//     // }
// }

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