UVA 11995 I Can Guess the Data Structure!

7709 단어 struct
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
"); else if(isq + iss + isp == 0) printf("impossible
"); else printf("%s
", isq ? "queue" : (iss ? "stack" : "priority queue")); } int main() { while(scanf("%d", &N) == 1) { init(); solve(); } return 0; }

좋은 웹페이지 즐겨찾기