[UVA] 11995 - I Can Guess the Data Structure! [STL 적용]

11626 단어 struct

11995 - I Can Guess the Data Structure!


Time limit: 1.000 seconds


Problem I


I Can Guess the Data Structure!


There is a bag-like data structure, supporting two operations:
1 x

Throw an element x into the bag.
2

Take out an element from the bag.
Given a sequence of operations with return values, you're going to guess the data structure. It is a stack (Last-In, First-Out), a queue (First-In, First-Out), a priority-queue (Always take out larger elements first) or something else that you can hardly imagine!

Input


There are several test cases. Each test case begins with a line containing a single integer n (1<=n<=1000). Each of the next n lines is either a type-1 command, or an integer 2 followed by an integer x. That means after executing a type-2 command, we get an element x without error. The value of x is always a positive integer not larger than 100. The input is terminated by end-of-file (EOF). The size of input file does not exceed 1MB.

Output


For each test case, output one of the following:
stack

It's definitely a stack.
queue

It's definitely a queue.
priority queue

It's definitely a priority queue.
impossible

It can't be a stack, a queue or a priority queue.
not sure

It can be more than one of the three data structures mentioned above.

Sample Input

6

1 1

1 2

1 3

2 1

2 2

2 3

6

1 1

1 2

1 3

2 3

2 2

2 1

2

1 1

2 2

4

1 2

1 1

2 1

2 2

7

1 2

1 5

1 1

1 3

2 5

1 4

2 4


Output for the Sample Input

queue

not sure

impossible

stack

priority queue


Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua UniversitySpecial Thanks: Yiming LiNote: Please make sure to test your program with the gift I/O files before submitting!
 
문제 풀이: STL에서queue,stack,priorityqueue의 사용.
코드:
 
 1 #include<cstdio>

 2 #include<cstring>

 3 #include<stdbool.h>

 4 #include<cmath>

 5 #include<queue>

 6 #include<stack>

 7 #include<algorithm>

 8 

 9 

10 #define rep(i,a,b)      for(i=(a);i<=(b);i++)

11 #define red(i,a,b)      for(i=(a);i>=(b);i--)

12 #define clr(x,y)        memset(x,y,sizeof(x))

13 #define sqr(x)          ((x)*(x))

14 

15 using namespace std;

16 

17 int i,j,x,y,pri,qui,sti;

18     

19 void check()

20 {

21     if(qui==1 && pri==0 && sti==0) printf("queue
"); 22 else 23 if(qui==0 && pri==1 && sti==0) printf("priority queue
"); 24 else 25 if(qui==0 && pri==0 && sti==1) printf("stack
"); 26 else 27 if(qui==0 && pri==0 && sti==0) printf("impossible
"); 28 else 29 printf("not sure
"); 30 } 31 32 int main() 33 { 34 int T; 35 36 37 38 while(scanf("%d",&T)!=EOF) { 39 pri=qui=sti=1; 40 41 queue <int> Q; 42 stack <int> S; 43 priority_queue <int> prQ; 44 45 while(T--) { 46 scanf("%d%d",&x,&y); 47 if(x==1) { 48 Q.push(y); 49 S.push(y); 50 prQ.push(y); 51 } 52 else { 53 54 if(qui==1) { 55 if(Q.empty() || Q.front()!=y) qui=0; 56 if(!Q.empty()) Q.pop(); 57 } 58 59 if(sti==1) { 60 if(S.empty() || S.top()!=y) sti=0; 61 if(!S.empty()) S.pop(); 62 } 63 64 if(pri==1) { 65 if(prQ.empty() || prQ.top()!=y) pri=0; 66 if(!prQ.empty()) prQ.pop(); 67 } 68 } 69 } 70 71 check(); 72 } 73 74 return 0; 75 }

좋은 웹페이지 즐겨찾기