题目链接:http://codeforces.com/contest/1154
题目大意
给定一个序列,每次老师把序列中的最大值及其附近的
k个人(如果不足则割舍)加到他的阵营,总共有两名老师轮番
做这个操作,输出一个序列表示每个人都在哪个阵营.
题目分析
k和n的数量级都是五次方,很迷惑人,
其实不难发现每个数只会被用到一次,
那么我们不妨用链表来跳跃性的映射关系,
初始化前后链表和映射好位置数组后,
我们对于每个没被占用的最大值,可以往左右各自找到
一个第一个未被占用的位置并且得到这两个位置后调整前后链表.
每次模拟可以直接在位置上打标记即可.
用数据结构什么的反而麻烦.
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=2e5+100;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);
}
/*
题目大意:
给定一个序列,每次老师把序列中的最大值及其附近的
k个人(如果不足则割舍)加到他的阵营,总共有两名老师轮番
做这个操作,输出一个序列表示每个人都在哪个阵营.题目分析:
k和n的数量级都是五次方,很迷惑人,
其实不难发现每个数只会被用到一次,
那么我们不妨用链表来跳跃性的映射关系,
初始化前后链表和映射好位置数组后,
我们对于每个没被占用的最大值,可以往左右各自找到
一个第一个未被占用的位置并且得到这两个位置后调整前后链表.
每次模拟可以直接在位置上打标记即可.
用数据结构什么的反而麻烦.
*/
int n,k,a[maxn];
int nxt[maxn],pre[maxn];
int pos[maxn],ans[maxn];
void getv(int& l,int cnt,int cur){while(l<=n){l=nxt[l];if(ans[l]==0){if(cnt){cnt--;ans[l]=cur;}else{return ;}}}
}
int main(){cin>>n>>k;nxt[0]=1;rep(i,1,n+1){cin>>a[i];pos[a[i]]=i;nxt[i]=i+1,pre[i]=i-1;}int cur=1;for(int i=n;i>=1;i--){if(ans[pos[i]]) continue;cur^=1;int l=pos[i],r=pos[i],cnt=k;while(1){r=nxt[r];if(r>n) break;if(ans[r]==0){if(cnt) cnt--,ans[r]=cur+1;else break;}}cnt=k;while(1){l=pre[l];if(l<1) break;if(ans[l]==0){if(cnt) cnt--,ans[l]=cur+1;else break;}}nxt[l]=r,pre[r]=l,ans[pos[i]]=cur+1;}rep(i,1,n+1) cout<<ans[i];return 0;
}