Pop Sequence

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:

Sample Output:

# include <iostream>
# include <cmath>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <string>
# include <map>
# include <set>
# include <list>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
# include <iomanip>
# include <sstream>
# include <bitset>

typedef long long ll;
const double PI = acos(-1);
template <typename T> 
void read(T &val) {
    
	T x = 0; 
	int bz = 1; 
	char c; 
	
	for (c = getchar(); (c<'0' || c>'9') && c != '-'; 
	c = getchar()); 
	
	if (c == '-') {
    
		bz = -1; 
		c = getchar(); 
	}
	
	for (; c >= '0' && c <= '9'; c = getchar()) 
		x = x * 10 + c - 48; 
		
	val = x * bz; 
}

void put(int x){
     
    static char	s[20];  
    int bas;  
  
    if(x < 0) {
     
        putchar('-');  
        x = -x;  
    }  
    
    if(x == 0) {
     
        putchar('0');  
        return;  
    }  
    
    bas = 0;  
    for(;x;x/=10) 
		s[bas++] = x%10+'0';  
		
    for(;bas--;) 
		putchar(s[bas]);  
}  

const int MAXN = 1e3 + 5;
int a[MAXN];
std::stack<int> stk;
std::stack<int> stk2;
std::queue<int> que;

int main() {
   
	int m;		// Stack size
	int n;		// Number length
	int k;		// Test case
	
	std::cin >> m >> n >> k;
	
	while (k--) {
   		
		while (!que.empty()) {
   
			que.pop();
		}
		
		while (!stk.empty()) {
   
			stk.pop();
		}
		
		while (!stk2.empty()) {
   
			stk2.pop();
		}
		
		for (int i=n; i>0; i--) {
   
			stk.push(i); 
		}
		
		for (int i=0; i<n; i++) {
   
			int t;
			std::cin >> t;
			que.push(t); 	
		}
		
		while (que.size()) {
   
			if (!stk2.empty()) {
   
				if (que.empty()) {
   
					std::cout << "YES\n";
					goto A;
				}
				
				if (stk2.top() == que.front()) {
   
					stk2.pop();
					que.pop();
				} else {
   
					if (!stk.empty()) {
   
						stk2.push(stk.top());
						stk.pop(); 
						
						if (stk2.size() > m) {
   
							std::cout << "NO\n";
							goto A;
						}
					} else {
   
						if (stk2.top() != que.front()) {
   
							std::cout << "NO\n";
							goto A;
						} else {
   
							stk2.pop();
							que.pop();
						}
					}
				}
			} else {
   
				if (stk.empty()) {
   
					if(que.empty()) {
   
						std::cout << "YES\n";
						goto A;
					} else {
   
						std::cout << "NO\n";
						goto A;
					}
				} else {
   
					if (stk.top() != que.front()) {
   
						stk2.push(stk.top());
						stk.pop(); 
						
						if (stk2.size() > m) {
   
							std::cout << "NO\n";
							goto A;
						}
					} else {
   
						stk.pop();
						que.pop();
					}
				}
			}
			
		}
		
		if (stk.empty() && stk2.empty() && que.empty()) {
   
			std::cout << "YES\n";
		} else {
   
			std::cout << "NO\n";
		}
		
		A: {
   };
	}
	
	return 0;
}