fork download 
  1.  
  2.  
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5. import java.io.InputStream;
  6. import java.util.InputMismatchException;
  7. import java.util.Arrays;
  8.  
  9.  
  10. // Start Implementation of Stack data structure
  11. class ArrayStack<T>
  12. {
  13. 	final int STACK_DEFAULT_SIZE = 10;
  14. 	int capacity ;
  15. 	int size = 0;
  16. 	T[] stock;
  17.  
  18. 	@SuppressWarnings("unchecked")
  19. 	ArrayStack()
  20. 	{
  21. 		capacity = STACK_DEFAULT_SIZE;
  22. 		stock =  (T[]) new Object[capacity];
  23. 	}
  24.  
  25. 	@SuppressWarnings("unchecked")
  26. 	ArrayStack(int capacity)
  27. 	{
  28. 		this.capacity = capacity;
  29. 		stock = (T[]) new Object[capacity];
  30. 	}
  31.  
  32. 	public boolean push(T elem)
  33. 	{
  34. 		if(size == stock.length)
  35. 		{
  36. 			int newSize = size + size >> 1;
  37. 			stock = Arrays.copyOf(stock, newSize);
  38. 		}
  39.  
  40. 		stock[size++] = elem;
  41. 		return true;
  42. 	}
  43.  
  44. 	public T pop()
  45. 	{
  46. 		if(isEmpty())
  47. 			return null;
  48.  
  49. 		T val = stock[--size];
  50. 		stock[size] = null;
  51. 		return val;
  52. 	}
  53.  
  54. 	public T peep()
  55. 	{
  56. 		if(isEmpty())
  57. 			return null;
  58.  
  59. 		return stock[size-1];
  60. 	}
  61.  
  62. 	public boolean isEmpty()
  63. 	{
  64. 		return size == 0;
  65. 	}
  66.  
  67. 	public int size()
  68. 	{
  69. 		return size;
  70. 	}
  71.  
  72. 	public boolean isContains(T elem)
  73. 	{
  74. 		boolean found = false;
  75.  
  76. 		for(int i=size-1; i>=0; i--)
  77. 		{
  78. 			if(stock[i].equals(elem))
  79. 			{
  80. 				found = true;
  81. 				break;
  82. 			}
  83. 		}
  84. 		return found;
  85. 	}
  86.  
  87. 	public void clear()
  88. 	{
  89. 		for(int i=0; i<size; i++)
  90. 		{
  91. 			stock[i] = null;
  92. 		}
  93.  
  94. 		size = 0;
  95. 	}
  96.  
  97. 	public String toString()
  98. 	{
  99. 		StringBuilder sb = new StringBuilder();
  100. 		sb.append("[");
  101. 		for(int i=size-1; i>=0; i--)
  102. 		{
  103. 			sb.append(stock[i]);
  104.  
  105. 			if(i >0)
  106. 				sb.append(",");
  107. 		}
  108.  
  109. 		sb.append("]");
  110.  
  111. 		return sb.toString();
  112. 	}
  113.  
  114. }
  115.  
  116. // END implementation of stack data structure
  117.  
  118. class StreetParadeProblem
  119. {
  120. 	public static void main(String[] args)throws IOException
  121. 	{
  122. 		Scan sc = new Scan();
  123. 		PrintWriter pr = new PrintWriter(System.out);
  124.  
  125. 		while(true)
  126. 		{
  127. 			int n = sc.scanInt();
  128.  
  129. 			if(n == 0)
  130. 				break;
  131.  
  132. 			ArrayStack<Integer> stack = new ArrayStack<>();
  133. 			int[] arr = new int[n+1];
  134. 			arr[0] = -1;
  135.  
  136. 			// without using an extra array
  137. 			// for(int i=0; i<n; i++)
  138. 				// arr[i+1] = sc.scanInt();
  139.  
  140. 			boolean isOrdered = true;
  141. 			int count = 1, number;
  142. 			for(int i=0; i<n; i++)
  143. 			{
  144. 				// System.out.println("i: " + i + " n: " +n + " count: " + count);
  145. 				// number = arr[i+1];
  146. 				number = sc.scanInt();
  147.  
  148. 				while(stack.peep() != null && stack.peep() == count)
  149. 				{
  150. 					// pr.print(stack.pop() + " ");
  151. 					// System.out.println("From 2");
  152. 					stack.pop();
  153. 					count++;
  154. 				}
  155.  
  156. 				if(number == count)
  157. 				{
  158. 					// System.out.println("From 1");
  159. 					count++;
  160. 				}
  161. 				else
  162. 				{
  163.  
  164.  
  165. 					if(stack.peep() == null || stack.peep() > number)
  166. 					{
  167. 						// System.out.println("From 3");
  168. 						stack.push(number);
  169. 					}
  170. 					else if(stack.peep() <= number)
  171. 					{
  172. 						// System.out.println("From 4");
  173. 						isOrdered = false;
  174. 						// break;
  175. 					}
  176. 				}
  177. 				// else
  178. 					// pr.println("From 5");
  179.  
  180. 				// System.out.println("stack: " + stack.toString());
  181. 			}
  182.  
  183. 			// pr.println();
  184.  
  185. 			if(isOrdered)
  186. 				pr.println("yes");
  187. 			else
  188. 				pr.println("no");
  189. 		}	
  190.  
  191. 		sc.close();
  192. 		pr.close();
  193. 	}
  194.  
  195. 	// Start Implementation of faster input
  196. 	static class Scan
  197. 	{
  198. 		private int index, total;
  199. 		private byte[] buf = new byte[1024];
  200. 		private InputStream in;
  201.  
  202. 		public Scan()
  203. 		{
  204. 			in = System.in;
  205. 		}
  206.  
  207. 		public int scan()throws IOException
  208. 		{
  209. 			if(total < 0)
  210. 				throw new InputMismatchException();
  211.  
  212. 			if(index >= total)
  213. 			{
  214. 				index = 0;
  215. 				total = in.read(buf);
  216.  
  217. 				if(total <=0)
  218. 					return -1;
  219. 			}
  220.  
  221. 			return buf[index++];
  222. 		}
  223.  
  224.  
  225. 		public int scanInt()throws IOException
  226. 		{
  227. 			int integer = 0;
  228.  
  229. 			int n = scan();
  230.  
  231. 			while(isWhiteSpace(n))
  232. 				n = scan();
  233.  
  234. 			int neg = 1;
  235.  
  236. 			if(n =='-')
  237. 			{
  238. 				neg = -1;
  239. 				n = scan();
  240. 			}
  241.  
  242. 			while(!isWhiteSpace(n))
  243. 			{
  244. 				if(n >='0' && n <= '9')
  245. 				{
  246. 					integer *= 10;
  247. 					integer += n-'0';
  248. 					n = scan();
  249. 				}
  250. 				else
  251. 					throw new InputMismatchException();
  252. 			}
  253.  
  254. 			return neg*integer;
  255. 		}
  256.  
  257. 		public boolean isWhiteSpace(int n)
  258. 		{
  259. 			if(n == ' ' || n == '\n' || n == '\t' || n == '\r' || n == -1)
  260. 				return true;
  261.  
  262. 			return false;
  263. 		}
  264.  
  265.  
  266. 		public void close()throws IOException
  267. 		{
  268. 			if(in != null)
  269. 				in.close();
  270. 		}
  271. 	}
  272.  
  273. 	// END implementation of faster input 
  274.  
  275.  
  276. }
Success #stdin #stdout 0.1s 27968KB
comments (?)
stdin 
5
4 1 2 5 3
10
1 2 10 5 4 3 9 8 7 6
5 
3 1 2 5 4
10 
6 1 5 2 4 3 7 10 8 9
5 
4 1 5 3 2 
5 
3 1 2 5 4 
5 
5 3 2 1 4 
10 
1 2 10 5 4 3 7 6 8 9 
10 
1 2 10 5 4 3 9 8 7 6 
5 
3 5 2 4 1 
5 
1 2 4 3 5 
4 
4 2 3 1 
0
stdout 
no
yes
yes
yes
no
yes
yes
yes
yes
no
yes
no
https://ideone.com/4QPyxS
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!