求助HACK or DEBUG
  • 板块P3509 [POI2010] ZAB-Frog
  • 楼主WsW_花逝爆零人
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/12/14 19:24
  • 上次更新2024/12/14 21:37:40
查看原帖
求助HACK or DEBUG
349824
WsW_花逝爆零人楼主2024/12/14 19:24
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1e6+5;
ll p[MAXN];
int lg2[MAXN];
int to[21][MAXN];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,k;ll m;cin>>n>>k>>m;
	for(int i=1;i<=n;i++)cin>>p[i];
	int l=1,r=k+1;
	lg2[0]=-1;
	for(int i=1;i<=n;i++){
		lg2[i]=lg2[i>>1]+1;
		while(r<n&&p[r+1]-p[i]<p[i]-p[l]){
			l++;
			r++;
		}
		to[0][i]=(p[r]-p[i]>p[i]-p[l]?r:l);
//		cout<<i<<":"<<l<<"->"<<r<<' '<<to[0][i]<<'\n';
	}
	for(int k=1;k<=lg2[n];k++){
		for(int i=1;i<=n;i++){
			to[k][i]=to[k-1][to[k-1][i]];
		}
	}
	for(int i=1;i<=n;i++){
		int now=i;
		for(int j=0;j<=lg2[n];j++){
			if(m&(1<<j)){
				now=to[j][now];
//				cout<<j<<' '<<ans<<'\n';
			}
		}
		cout<<now<<'\n';
	}
	return 0;
}
2024/12/14 19:24
加载中...