cjb-poi2010frog

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
#define N 1000010
int n,k;
long long m;
long long a[N];
int f[N],ans[N],tmp[N];
int main()
{
    cin>>n>>k>>m;
    rep(i,n)scanf("%lld",&a[i]);
    int l=1,r=k+1;
    rep(i,n)
    {
        while (r<n && a[r+1]-a[i]<a[i]-a[l])l++,r++;
        if (a[r]-a[i]>a[i]-a[l])f[i]=r; else f[i]=l;
    }

    rep(i,n)ans[i]=i;
    while (m)
    {
        if (m&1)rep(i,n)ans[i]=f[ans[i]];
        rep(i,n)tmp[i]=f[i];
        rep(i,n)f[i]=tmp[f[i]];
        m>>=1;
    }
    rep(i,n)printf("%d%c",ans[i],i==n?'\n':' ');
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
#define N 1000010
int n,k;
long long m;
long long a[N];
int f[N],ans[N],tmp[N];
int main()
{
    cin>>n>>k>>m;
    rep(i,n)scanf("%lld",&a[i]);
    int l=1,r=k+1;
    rep(i,n)
    {
        while (r<n && a[r+1]-a[i]<a[i]-a[l])l++,r++;
        if (a[r]-a[i]>a[i]-a[l])f[i]=r; else f[i]=l;
    }
    rep(i,n)ans[i]=i;
    while (m)
    {
        if (m&1)rep(i,n)ans[i]=f[ans[i]];
        rep(i,n)tmp[i]=f[i];
        rep(i,n)f[i]=tmp[f[i]];
        m>>=1;
    }
    rep(i,n)printf("%d%c",ans[i],i==n?'\n':' ');
    return 0;
}