#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;
}
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;
}
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;
}
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;
}
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(l+1,r,r); dfs(r,n,r);
for(int i=1;i<=n;++i) answer(i,pos[i]);
}
/**
4,1,3,5,2
*/
#ifdef unx
main(){
n=5;
a[1]=4, a[2]=1, a[3]=3, a[4]=5, a[5]=2;
solve(n);
return 0;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
//cout<<solve(n)<<"\n";
solve(n);
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Incorrect |
5 ms |
512 KB |
Wrong Answer [4] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Incorrect |
5 ms |
512 KB |
Wrong Answer [4] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Incorrect |
5 ms |
512 KB |
Wrong Answer [4] |
4 |
Halted |
0 ms |
0 KB |
- |