Submission #233344

#	Time	Username	Problem	Language	Result	Execution time	Memory
233344		LittleFlowers__	Xylophone (JOI18_xylophone)	C++14	47 / 100	179 ms	47072 KiB

xylophone

#include <iostream>
using namespace std;

//#define unx xun

#ifndef unx
#include "xylophone.h"
#endif

#ifdef unx

int n;
int a[5010];

int query(int s,int t){
    int mx=0, mn=5000;
    for(int i=s;i<=t;++i) mx=mx>a[i]?mx:a[i], mn=mn>a[i]?a[i]:mn;
    return mx-mn;
}
void answer(int i,int val){
    cout<<val<<" ";
}

#endif

int ans[5010], pos[5010];
int asked[5010][5010], dd[5010][5010];

int ask(int s,int t){
    if(asked[s][t]) return asked[s][t]; else return asked[s][t]=query(s,t);
}

void dfs(int l,int r,int p){
    if(l>=r || dd[l][r]++) return;
    if(p<0){ p=-p;
        if(p==l){
            int val=ask(l,r), t=l;
            for(int j=12;j>=0;--j){
                t+=1<<j;
                if(t<=r && ask(l,t)<val); else t-=1<<j;
            } t++;
            ans[val+pos[p]]=t; pos[t]=val+pos[p];
            dfs(l+1,t,t); dfs(t,r,t);
        } else{
            int val=ask(l,r), t=r;
            for(int j=12;j>=0;--j){
                t-=1<<j;
                if(t>=l && ask(t,r)<val); else t+=1<<j;
            } t--;
            ans[val+ans[p]]=t; pos[t]=val+pos[p];
            dfs(l,t,t); dfs(t,r-1,t);
        }
    } else{
        if(p==l){
            int val=ask(l,r), t=l;
            for(int j=12;j>=0;--j){
                t+=1<<j;
                if(t<=r && ask(l,t)<val); else t-=1<<j;
            } t++;
            ans[pos[p]-val]=t; pos[t]=pos[p]-val;
            dfs(l+1,t,-t); dfs(t,r,-t);
        } else{
            int val=ask(l,r), t=r;
            for(int j=12;j>=0;--j){
                t-=1<<j;
                if(t>=l && ask(t,r)<val); else t+=1<<j;
            } t--;
            ans[pos[p]-val]=t; pos[t]=pos[p]-val;
            dfs(l,t,-t); dfs(t,r-1,-t);
        }
    }
}

void solve(int n){
    int l=1,r=n;
    for(int i=12;i>=0;--i){
        l+=1<<i;
        if(l<=n && ask(l,r)==n-1); else l-=1<<i;
    }
    for(int i=12;i>=0;--i){
        r-=1<<i;
        if(l<=r && ask(l,r)==n-1); else r+=1<<i;
    }
    ans[1]=l, ans[n]=r, pos[l]=1, pos[r]=n;
    dfs(1,l,-l); dfs(l,r-1,-l); dfs(r,n,r);
    for(int i=1;i<=n;++i) answer(i,pos[i]);
}

/**
4,1,3,5,2
*/

#ifdef unx
main(){
    freopen("tmp.inp","r",stdin);

    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    //cout<<solve(n)<<"\n";
    solve(n);
}
#endif

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 0 / 53