TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3351
  • 题目
  • P3351【THOI2015】解密运算
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    小J是一位勤奋的大学生,在清华大学计算机系学习的他,每天都会遇到不少有挑战性的问题。
    今天,小J的老师在课上讲了一个字符串的加密算法,对于一个长度为N的字符串,我们在字符串的末尾添加一个特殊的字符“.”。之后将字符串试作一个环,从位置1,2,3,...,N+1为起点读出N+1个字符,就能得到N+1个字符串。比如对于字符串“ABCAAA”,我们可以得到这N+1个串:

    ABCAAA.
    BCAAA.A
    CAAA.AB
    AAA.ABC
    AA.ABCA
    A.ABCAA
    .ABCAAA

    接着我们对得到的这N+1个串按字典序从小到大进行排序(注意特殊字符“.”的字典序小于任何其它的字符)结果如下:

    .ABCAAA
    A.ABCAA
    AA.ABCA
    AAA.ABC
    ABCAAA.
    BCAAA.A
    CAAA.AB

    最后,将排序后的N+1个串的最后一个字符取出,按照顺序排成一个新的字符串,也就是上面这个表的最后一列,就是加密后的密文“AAAC.AB”。
    聪明的小J很快就理解了加密算法,然而因为课堂的时间有限,老师没有来得及讲解密算法就下课了。好奇的小J很想知道如何对字符串进行解密,即通过加密后的密文求出加密前的字符串。你能帮他解决这个问题吗?

    输入格式

    第一行有两个整数N,M,分别表示加密前的字符串长度和字符集的大小,其中字符用整数1,2,3,...,M编号,添加的特殊字符“.”用0编号。
    第二行为N+1个整数,表示加密后的字符串。

    输出格式

    输出仅一行,包含N个整数,用空格隔开,依次表示加密前字符串中每个字符的编号。

    样例输入

    6 3
    1 1 1 3 0 1 2

    样例输出

    1 2 3 1 1 1 

    提示

    【样例说明】
    将样例输入与输出中的1,2,3分别视为A,B,C,则样例即为题目描述所述的字符串
    【数据规模】
    N≤200000,M≤200000