P3509
  • 板块题目总版
  • 楼主huang_ak_IOI
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/6/16 18:29
  • 上次更新2023/10/27 23:12:55
查看原帖
P3509
330418
huang_ak_IOI楼主2022/6/16 18:29
#include<bits/stdc++.h>
//#include<graphics.h>
#define int long long
using namespace std;
/*
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<='0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
*/
int f[1000005],ff[1000005],ans[1000005],a[1000005];
int n,k,m;
signed main(){
    //freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//std::ios::sync_with_stdio(false);
	cin>>n>>k>>m;
	for(register int i=1;i<=n;i++){
		cin>>a[i];
		ans[i]=i;
	}
	f[1]=k+1;
	int l=1,r=k+1;
	for(register int i=2;i<=n;i++){
		if(r+1<=n && a[i]-a[l]>a[r+1]-a[i]) l++,r++;
		if(a[i]-a[l]>=a[r]-a[i]) f[i]=l;
		else f[i]=r;
	}
	while(m){
		if(m&1) for(register int i=1;i<=n;i++) ans[i]=f[ans[i]];
		m/=2;
		memcpy(ff,f,sizeof(ff));
		for(register int i=1;i<=n;i++) f[i]=ff[ff[i]];
	}
	for(register int i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
}


2022/6/16 18:29
加载中...