【codeforces】Codeforces Round #552 (Div. 3) E. Two Teams

题目链接：http://codeforces.com/contest/1154/problem/E

题解：数组模拟链表，按照操作模拟。

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e5+10;
int b[maxn];
struct node 
{
	int x,id;
}a[maxn];
int fa[maxn],so[maxn];
int cmp(node x,node y)
{
	return x.x>y.x;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].x);
		a[i].id=i;
		fa[i]=i-1;
		so[i]=i+1;
	}
	sort(a+1,a+n+1,cmp);
	int temp=1;
	for(int i=1;i<=n;i++)
	{
		if(b[a[i].id])	continue; 
		int z=0,j;

		b[a[i].id]=temp;
		for(j=so[a[i].id];j<=n&&z<m;j=so[j])
		{
			if(b[j]==0)
			{
				b[j]=temp;
				z++;
			}
			if(z==m)	break;
		}
		so[a[i].id]=j;		//链表连接 
		
		z=0;
		for(j=fa[a[i].id];j>=1&&z<m;j=fa[j])
		{
			if(b[j]==0)
			{
				b[j]=temp;
				z++;
				
			}
			if(z==m)	break;
		}
		fa[a[i].id]=j;		//链表连接 
		
		if(temp==1)
		{
			temp=2;
		}
		else
			temp=1;
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d",b[i]);
	}
	return 0;
}