#P5262. [ROI2007 / JSOI2013] 体育课

    ID: 4227 Type: RemoteJudge 1000ms 250MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2013各省省选江苏O2优化

[ROI2007 / JSOI2013] 体育课

题目描述

体育课里一共有 NN 个同学,学号从 11NN。JYY 的体育老师 KFC 有一个特殊排队方法:

  • KFC 先让班里的 NN 个同学按照学号从小到大的顺序,从左到右站成一排,然后从到队列的最左边(也就是第一个学生面前)开始,一直向右走动到第 N1N-1 个学生面前;
  • 接着 KFC 再回到第一个学生面前,继续开始向右走,就这样一共走动 N1N-1 次。
  • 每次当 KFC 走到第 ii 个学生面前时,KFC 会比较一下队列里第 ii 个学生和第 i+1i+1 个学生的身高,如果左边(第 ii 个)的学生比右边(第 i+1i+1 个)的学生高,那么 KFC 就会交换这两个学生在队列里的位置。

最终,在 N1N-1 次走动全部结束之后,KFC 会选出队列最右边的一些学生去搬桌子。自然地,JYY 希望能够站在尽量靠左的位置来增加自己踢足球的机会。

此外,JYY 还有一个绝招,那就是在 KFC 老师快走到自己面前的时候,开始蹲下来系鞋带!如果 JYY 蹲下来系鞋带了,那么在这一次走动中,好说话的 KFC 老师就不会让 JYY 和相邻的同学比较身高了,自然也就不会让 JYY 和相邻的同学交换位置(只有 JYY 最聪明会蹲下来系鞋带,其他同学都只会老老实实的让 KFC 老师比较身高)。

蹲下来系鞋带是很耗费体力的。为了留着体力踢足球,JYY 最多只能蹲下 KK 次。

JYY 想知道,按照怎样的下蹲策略可以使自己在队列里站的尽量靠左。用一个长度为 N1N-1 的字符串来表示一个策略:如果字符串的第 ii 个字符是 +,则表示在第 ii 次走动时 JYY 蹲下来系鞋带;如果第 ii 个字符是 -,则表示 JYY 会老老实实地比较身高。

输入格式

第一行包含三个整数 N,P,KN,P,K,分别表示同学的数量、JYY 的学号、JYY 最多能蹲下的次数。

第二行包含 NN 个整数,其中第 ii 个整数表示 hih_i,表示学号为 ii 的同学的身高。

输出格式

第一行包含一个正整数,表示按照最佳策略时 JYY 可以排在的最靠左的位置。

第二行包含一个长度为 N1N-1 的字符串,表示最佳策略。如果有多个最佳策略,JYY 希望知道字典序最大的策略。

10 7 7
8 3 5 4 5 7 4 2 1 3
3
----+++++

提示

数据范围:1PN1051\le P\le N\le 10^50KN10\le K\le N-11hi1091\le h_i\le 10^9