学步园

UVA_11995

    如果还可能是某个数据结构的话，就对其模拟操作，知道出现错误为止。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 1010
int N, D, max[4 * MAXD], q[MAXD], s[MAXD];
void init()
{
    for(D = 1; D < N + 2; D <<= 1);
    memset(max, 0, sizeof(max[0]) * 2 * D);
}
void update(int i)
{
    for(; i ^ 1; i >>= 1)
        max[i >> 1] = std::max(max[i], max[i ^ 1]);    
}
void Pop()
{
    int i;
    for(i = 1; i < D;)
    {
        if(max[i << 1] == max[i]) i <<= 1;
        else i = i << 1 | 1;    
    }
    max[i] = 0, update(i);
}
void solve()
{
    int i, op, x, front, rear, top, isq, iss, isp;
    front = rear = top = 0;
    isq = iss = isp = 1;
    for(i = 0; i < N; i ++)
    {
        scanf("%d%d", &op, &x);
        if(op == 1)
        {
            if(isq) q[rear ++] = x;
            if(iss) s[top ++] = x;
            if(isp) max[D + i] = x, update(D + i);    
        }
        else
        {
            if(isq)
            {
                if(front == rear) isq = 0;
                else
                {
                    if(q[front] != x) isq = 0;
                    ++ front;    
                }    
            }
            if(iss)
            {
                if(top == 0) iss = 0;
                else
                {
                    -- top;
                    if(s[top] != x) iss = 0;    
                }    
            }
            if(isp)
            {
                if(max[1] != x) isp = 0;
                else Pop();
            }
        }
    }    
    if(isq + iss + isp > 1)
        printf("not sure\n");
    else if(isq + iss + isp == 0)
        printf("impossible\n");
    else printf("%s\n", isq ? "queue" : (iss ? "stack" : "priority queue"));
}
int main()
{
    while(scanf("%d", &N) == 1)
    {
        init();
        solve();    
    }
    return 0;    
}