Submission #745229

#	Time	Username	Problem	Language	Result	Execution time	Memory
745229		WKYH	Permutation (APIO22_perm)	C++17	91.33 / 100	3 ms	340 KiB

perm

#include<bits/stdc++.h>
#define qc ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rt return
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vecin(a) for(auto &d:a)cin>>d;
typedef long long int ll;
const long long mod=1e9+7;
const int int_inf=2147483647;
const long long int ll_inf=9223372036854775807;
const int alp_up=64;
const int alp_lw=96;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
using namespace std;
ll gcd(ll a,ll b){if(b==0)rt a;rt gcd(b,a%b);}
ll lcm(ll a,ll b){rt a/gcd(a,b)*b;}
void setIO(string name)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}

/*
int n;
vector<int>h;
vector<vector<int>>l,r,low,hgh;
void init(int N,vector<int>H)
{
    n=N;h=H;
    l.resize(20,vector<int>(n,-1));
    r.resize(20,vector<int>(n,-1));
    low.resize(20,vector<int>(n,-1));
    hgh.resize(20,vector<int>(n,-1));
    // monotonic stack for l and r
        // -1 means no target
    stack<int>s;
    for(int i=0;i<n;i++)
    {
        while(!s.empty()&&h[s.top()]<h[i])s.pop();
        if(!s.empty())l[0][i]=s.top();
        s.push(i);
    }
    while(!s.empty())s.pop();
    for(int i=n-1;i>=0;i--)
    {
        while(!s.empty()&&h[s.top()]<h[i])s.pop();
        if(!s.empty())r[0][i]=s.top();
        s.push(i);
    }
    // sparse table for l and r
    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            if(l[i-1][j]!=-1)l[i][j]=l[i-1][l[i-1][j]];
            if(r[i-1][j]!=-1)r[i][j]=r[i-1][r[i-1][j]];
        }
    }
    // sparse table for low and hgh
        // using dynamic programming
    for(int i=0;i<n;i++){
        if(l[0][i]==-1)hgh[0][i]=r[0][i];
        else if(r[0][i]==-1)hgh[0][i]=l[0][i];
        else if(h[l[0][i]]>h[r[0][i]]){
            hgh[0][i]=l[0][i];
            low[0][i]=r[0][i];
        }
        else{
            hgh[0][i]=r[0][i];
            low[0][i]=l[0][i];
        }
    }
    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            if(low[i-1][j]!=-1)low[i][j]=low[i-1][low[i-1][j]];
            if(hgh[i-1][j]!=-1)hgh[i][j]=hgh[i-1][hgh[i-1][j]];
        }
    }
    //for(auto c:l)cout<<c<<" ";cout<<"\n";
    //for(auto c:r)cout<<c<<" ";cout<<"\n";
    //for(auto c:tall){for(auto d:c)cout<<d<<" ";cout<<"\n";}
}
int tallest(int cur,int tar) // tallest tree in [cur,tar]
{
    for(int i=19;i>=0;i--){
        if(r[i][cur]==-1)continue;
        if(r[i][cur]>tar)continue;
        cur=r[i][cur];
    }
    rt cur;
}
int minimum_jumps(int a,int b,int c,int d)
{
    if(b+1==c)rt (r[0][b]<=d&&r[0][b]!=-1)? 1:-1; // no tree in [b+1,c-1]

    int t_cd=tallest(c,d); //tallest tree in [c,d]
    int t_bc=tallest(b+1,c-1); // tallest tree in [b+1,c-1]
    int cur=b,ans=0;

    // tallest tree from b to left, not higher than t_cd
    for(int i=19;i>=0;i--){
        if(l[i][cur]==-1)continue;
        if(l[i][cur]<a)continue;
        if(h[l[i][cur]]>h[t_cd])continue;
        cur=l[i][cur];
    }
    if(h[cur]>h[t_bc]){ // straight away jump to [c,d]
        rt (r[0][cur]<=d&&r[0][cur]!=-1)? 1:-1;
    }

    // choose higher edge to jump, not higher than h[t_bc]
    for(int i=19;i>=0;i--){
        if(hgh[i][cur]==-1)continue;
        if(h[hgh[i][cur]]>h[t_bc])continue;
        cur=hgh[i][cur];
        ans+=(1<<i);
    }
    if(cur==t_bc)rt (r[0][cur]<=d&&r[0][cur]!=-1)? ans+1:-1;

    // any jump will cause h[cur] > h[t_bc]
    if(l[0][cur]!=-1&&c<=r[0][l[0][cur]]&&r[0][l[0][cur]]<=d)rt ans+2; // consider left
    for(int i=19;i>=0;i--){ // consider right
        if(r[i][cur]==-1)continue;
        if(c<=r[i][cur])continue;
        cur=r[i][cur];
        ans+=(1<<i);
    }

    // jump to right suppose in [c,d]
    cur=r[0][cur];ans++;
    rt (c<=cur&&cur<=d)? ans:-1;
}

int xmain()
{
    init(7, {3, 2, 1, 6, 4, 5, 7});cout<<minimum_jumps(4, 4, 6, 6)<<" "<<minimum_jumps(1, 3, 5, 6)<<" "<<minimum_jumps(0, 1, 2, 2);
    //init(5,{5,1,2,3,4});cout<<minimum_jumps(1,1,4,4);
    //init(9,{9,6,4,2,1,3,5,7,8});cout<<minimum_jumps(0,0,1,1);
    //init(8,{1,2,3,4,5,6,7,8}); cout<<minimum_jumps(0,2,4,7);
    cout<<"\n";
    for(int i=0;i<9;i++){for(int j=i+1;j<9;j++)cout<<minimum_jumps(i,i,j,j)<<" ";cout<<"\n";}

    rt 0;
}
/*/

vector<int> construct_permutation(ll k)
{
    vector<int>a,ans;
    while(k>0){
        a.push_back(k%2);
        k/=2;
    }
    reverse(all(a));
    int z=a.size();
    for(int i=0;i<z-1;i++){
        ans.push_back(i);
    }
    int m=z-1;
    for(int i=1;i<z;i++){
        if(a[i]==0)continue;
        ans.insert(ans.begin()+(z-i-1),m);
        m++;
    }
    rt ans;
}
int xmain()
{
    //init(6,3);cout<<add_teleporter(3,4)<<add_teleporter(5,0)<<add_teleporter(4,5)<<add_teleporter(5,3)<<add_teleporter(1,4);
    //init(6,3);cout<<add_teleporter(5,0)<<add_teleporter(1,4)<<add_teleporter(2,4)<<add_teleporter(4,5);
    //init(6,6);for(int i=2;i<6;i++)for(int j=i+1;j<6;j++)cout<<add_teleporter(j,i);
    //init(5,1);cout<<add_teleporter(0,2)<<add_teleporter(3,0)<<add_teleporter(3,2)<<add_teleporter(2,3);
    vector<int>haha=construct_permutation(15);
    for(auto c:haha)cout<<c<<" ";
    rt 0;
}

//*/


/*
n=15;
15 = 1111 = 8+4+2+1
0,1,2 ->+8
0,1,3,2->+4
0,4,1,3,2
5,0,4,1,3,2
*/

Compilation message (stderr)

perm.cpp: In function 'void setIO(std::string)':
perm.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
perm.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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