Submission #1312427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312427		danglayloi1	순열 (APIO22_perm)	C++20	10 / 100	1095 ms	344 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;
}
ll mul(ll a, ll b)
{
    if(2e18/a<b) return 2e18;
    return a*b;
}
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
ll get(ll l, ll r)
{
    return l+mt()*mt()%(r-l+1);
}
ll dp[100000], pre[100000], suf[100000], rdp[nx];
vector<int> zip(vector<int> ve)
{
    vector<int> rar=ve;
    sort(rar.begin(), rar.end());
    for(int i = 0; i < ve.size(); i++)
        ve[i]=lower_bound(rar.begin(), rar.end(), ve[i])-rar.begin();
    return ve;
}
ll bit[100000];
void upd(int x, ll val)
{
    for(; x <= 200; x+=x&-x)
        bit[x]=add(bit[x], val);
}
ll get(int x)
{
    ll res=0;
    for(; x > 0; x-=x&-x)
        res=add(res, bit[x]);
    return res;
}
ll cal(vector<int> ve)
{
    ll sum=1;
    for(int i = 0; i < ve.size(); i++)
        dp[i]=0;
    for(int i = 0; i <= 200; i++)
        bit[i]=0;
    for(int i = 0; i < ve.size(); i++)
    {
        dp[i]=add(1, get(ve[i]));
        sum=add(sum, dp[i]);
        upd(ve[i]+1, dp[i]);
    }
    return sum;
}
void radd(int x, ll val)
{
    for(; x > 0; x-=x&-x)
        bit[x]=add(bit[x], val);
}
ll rget(int x)
{
    ll res=0;
    for(; x <= 200; x+=x&-x)
        res=add(res, bit[x]);
    return res;
}
ll rcal(vector<int> ve)
{
    ll sum=1;
    for(int i = 0; i <= 200; i++)
        bit[i]=0;
    for(int i = 0; i < ve.size(); i++)
        rdp[i]=0;
    for(int i = (int)ve.size()-1; i >= 0; i--)
    {
        rdp[i]=add(1, rget(ve[i]+2));
        sum=add(sum, rdp[i]);
        radd(ve[i]+1, rdp[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;
    while(true)
    {
        int len=200;
        cur=1;
        vector<int> ha;
        ha.clear();
        for(int i = 0; i < len; i++)
            ha.emplace_back(i);
        // shuffle(ha.begin()+65, ha.begin()+85, mt);
        int te=20;
        while(te--)
        {
            int i=get(1, len-1);
            swap(ha[i], ha[i-1]);
        }
        ve.clear();
        for(int i = 0; i < len; i++)
        {
            pair<ll, int> best={-1, -1};
            cur=cal(ve);
            rcal(ve);
            if(cur==k) break;
            pre[0]=1;
            for(int j = 0; j < ve.size(); j++)
            {
                if(j>0) pre[j]=pre[j-1];
                if(ve[j]<ha[i]) pre[j]=add(pre[j], dp[j]);
            }
            suf[ve.size()]=1;
            for(int j = ve.size()-1; j >= 0; j--)
            {
                suf[j]=suf[j+1];
                if(ve[j]>ha[i]) suf[j]=add(suf[j], rdp[j]);
            }
            for(int j = 0; j <= ve.size(); j++)
            {
                ll tmp;
                if(j==0) tmp=suf[j];
                else tmp=mul(pre[j-1], suf[j]);
                ll nxt=add(cur, tmp);
                if(nxt<=k)
                {
                    if(best.se==-1 || best.fi<nxt)
                        best={nxt, j};
                }
            }
            if(best.se==-1)  continue;
            ve.insert(ve.begin()+best.se, ha[i]);
            cur=best.fi;
            // if(cal(ve)!=best.fi)
            // {
            //     cout<<ha[i]<<'\n';
            //     for(int x:ve) cout<<x<<' ';
            //     cout<<'\n';
            //     for(int j = 0; j < ve.size(); j++)
            //         cout<<pre[j]<<' '<<suf[j]<<'\n';
            //     exit(0);
            // }
            if(cur==k) break;
        }
        // cerr<<cur<<' ';
        // for(int x:ve) cerr<<x<<' ';
        // cerr<<'\n';
        if(cur==k && ve.size()<=90) return zip(ve);
    }
    assert(0);
}
// int main()
// {
//     vector<int> ve=construct_permutation(90);
//     cout<<cal(ve)<<'\n';
//     for(int x:ve) cout<<x<<' ';
//     // for(int te = 1; te <= 100; te++)
//     // {
//     //     ll k=get(1, 1000000000000000000);
//     //     vector<int> ve=construct_permutation(k);
//     //     if(cal(ve)!=k) return cout<<"ha", 0;
//     //     ve=construct_permutation(k);
//     //     if(cal(ve)!=k) return cout<<"ha", 0;
//     //     cerr<<k<<'\n';
//     // }
// }

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