#17. 第三章 · 随便写的循环队列

内存限制:32 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Yt

题目描述

与此同时,Yt正在蛋糕店给大家准备lqq的生日蛋糕。由于Yt希望给地球人都分享一块lqq的生日蛋糕,他随便写了一个循环队列来记录待处理的蛋糕订单。每个订单都用一个int记录。部分代码如下:

int a[MAX_SIZE];
int front = 0, rear = -1; //尾指针和头指针

void enQueue(int x) //读入
{
    a[(++rear) % MAX_SIZE] = x;
} 

int deQueue(void) //输出
{
    return a[(front++) % MAX_SIZE];
}

但是这个循环队列的稳定性真的超级糟糕。比如说,连续向a中push进了超过个数据后,循环队列里只剩下了最后push进队列的个数据。这时再输出时,队列就不能符合FIFO(先进先出)的原则了。

蛋糕的制作和发放都需要时间,所以循环队列中的输入和输出顺序是不固定的,但输入输出次数都应当与订单数相等。第一天处理了块蛋糕后,Yt发现订单记录乱糟糟的,订单顺序,以及订单的内容都不对劲。这段循环队列的代码肯定要重做了。不过在重写代码之前,Yt想确认一下订单处理系统的其他代码有没有bug。

他整理出了个长度为的数列。其中第一个数列是纸质记录下来的,今天真正的订单数据,是按正确输出顺序记录的个订单编号(也是正确FIFO时输入输出的内容)。而其余的个数列是待确认的订单记录,里面只有一些是循环队列a的输出记录。请先帮Yt分类一下:个记录之中,哪些数列不可能是循环队列a输出出来的。

此外Yt保证:

一,每次用pop输出时,a[(front++) % MAX_SIZE]已经保存了某个数值,换言之,front%MAX_SIZE<=rear

二,

提示:

研究a的性质时,你会发现,在rear>=MAX_SIZE之后,a中保存的MAX_SIZE个int值,恰好是rear之前(含rear)的连续MAX_SIZE个输入值。所以对于待检测数列,只要确认每次pop时的rear值,就可以确认数列是否可以通过a得到了。这样的rear序列可能会有很多个,不过你只需要确认是否存在至少一个就可以了。

输入格式

第一行,输入,以空格分隔。

第二行,按顺序输入个整数,是今天真实的订单数据。

随后行,每行个整数,表示一组待验证的订单记录。

输出格式

行,每行输出一个字符,对应一条待验证记录。

当a能输出出来这条记录时输出Y,否则输出N

样例

样例输入:

6 4 3
1 2 3 4 5 2
1 5 3 4 5 2
4 2 3 1 5 2
1 1 1 1 1 1
1 3 5 7 9 11

样例输出:

Y
N
N
N

解释:

图片解释请翻到本题最下面。

第一条记录:读入1,2,3,输出1,读入4,5,输出5,3,4,5,读入2,输出2。

其余记录不能由a输出。

数据范围与提示

数据范围:

对于30%的数据,

对于80%的数据,

对于100%的数据,

所有数据都不超出int的范围。

另外Yt提供的代码段很可能没什么用。请好好判断你是否需要复制粘贴这段代码。

绘图by zyy

通告标题

通告内容

已知晓