Codeforces-1154E

佚名 6年前 (2019-04-17) 随笔 895人围观抢沙发百度已收录

E. Two Teams time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

There are nn students standing in a row. Two coaches are forming two teams — the first coach chooses the first team and the second coach chooses the second team.

The ii-th student has integer programming skill aiai. All programming skills are distinct and between 11 and nn, inclusive.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Firstly, the first coach will choose the student with maximum programming skill among all students not taken into any team, and kk closest students to the left of him and kk closest students to the right of him (if there are less than kk students to the left or to the right, all of them will be chosen). All students that are chosen leave the row and join the first team. Secondly, the second coach will make the same move (but all students chosen by him join the second team). Then again the first coach will make such move, and so on. This repeats until the row becomes empty (i. e. the process ends when each student becomes to some team).

Your problem is to determine which students will be taken into the first team and which students will be taken into the second team.

Input

The first line of the input contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the number of students and the value determining the range of chosen students during each move, respectively.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤n1≤ai≤n), where aiai is the programming skill of the ii-th student. It is guaranteed that all programming skills are distinct.

Output

Print a string of nn characters; ii-th character should be 1 if ii-th student joins the first team, or 2 otherwise.

Examples input

5 2
2 4 5 3 1

output

input

5 1
2 1 3 5 4

output

input

7 1
7 2 1 3 5 4 6

output

input

5 1
2 4 5 3 1

output

题目大意：有一队n个学生站成一排，每个学生有着其独特的编程能力值（保证这些值不重复），现有1号老师和2号老师轮流从队伍中挑选人（1号老师先选），每个老师每次会选择当前队伍中编程能力值最大的学生和其左右两边k个学生加入他的队伍，学生被选择后会离开队伍并且带上那个老师的序号（1或2），最后需要按学生的原顺序输出每一个学生的序号。

题解：使用stl里的链表即可完成该题的操作，详细操作见代码注释。

#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<map> #include<set> #include<stack> #include<queue> #include<list> #include<cstdio> #include<cmath> #include<cctype> #include<iomanip>
using namespace std; typedef long long ll; const int N = 200005; list<pair<int, int> > L;//构建一个内部为pair的链表
list<pair<int, int> >::iterator ite[N];//建立相应的每个学生的迭代器用于之后的访问
pair<int, int> a[N];//记录每个学生的数据，first是能力值，second是原编号
bool vis[N];//vis记录该编号是否访问过
int  ans[N];//ans按编号记录学生所属是1还是2
int main() { ios::sync_with_stdio(false); // freopen("D:\\in.txt","r",stdin); // freopen("D:\\out.txt","w",stdout);
    int n, k, team = 1;//team代表的是老师的编号，即只有1和2，初始为1
    cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i].first;//输入能力值
        a[i].second = i;//second是初始编号
        L.push_back(a[i]);//在链表中插入该学生
        ite[i] = --L.end();//相应的迭代器指向该学生
 } sort(a + 1, a + 1 + n);//排序，按学生的能力值从小到大
    for(int i = n; i >= 1; i--)//逆序遍历学生
 { int t = a[i].second;//提出学生的原编号
        if(vis[t])//访问过了，直接跳过下列步骤
            continue; list<pair<int, int> >::iterator l = ite[t], r = ite[t];//新建l和r两个迭代器来进行操作
        for(int i = 1; i <= k; i++)//出了该学生之外还要选两边的k个人
 { //迭代器分别向左向右移动，注意越界问题
            if(l != L.begin()) l--; if(r != --L.end()) r++; } r++; while(l != r)//开始进行删除（离队）操作
 { ans[l->second] = team;//按编号记录所在队伍
            vis[l->second] = true;//标记为以访问
            l = L.erase(l);//删除该节点
 } team = 3 - team;//该操作可以使老师编号在1和2之间来回更换
 } for(int i = 1; i <= n; i++) { cout << ans[i];//输出结果
 } //system("pause");
    return 0; }