fork download
copy 
  1. /*PROBLEM: QUICKSORT
  2. One of the algorithms to sort N distinct integers A[1], A[2],…, A[N], called Quick Sort, works as follows: Rearrange the array so that for a integer A[p],
  3. called the Pivot, it holds that if i<p then A[i]<A[p] and if i>p A[p]<A[i].
  4. Then, it recursively sorts A[1], A[2]…, A[p−1] and A[p+1], A[p+2], …, A[N].
  5. Write a program to count A[p] which already satisfies the above condition without any rearrangement. 
  6. - Time Limit: 2 seconds for at most 30 test cases. (If your program is in Java, then you have 4 seconds).
  7.   If your program exceeds the time limit, then it is terminated immediately.
  8.   You can still obtain partial scores (0< your score < full score) if your program gave right answers to at least one group of test cases.
  9.   However, in some cases your score might be zero even though your program gave right answers.
  10.   To prevent this, you are supposed to take the following step.
  11.   For C / C++, use "setbuf(stdout, NULL);" just once before your first call of printf.
  12.   For C++, use "setbuf(stdout, NULL);" as above and use "cout" instead of "printf" to obtain partial scores.
  13.   For Java, use "System.out.println".  ※ Check the provided sample code for details. 
  14.   If you get partial score even though your program ended within the time limit, it failed in some test cases.  
  15. - Memory Limit : heap, global, static 256MB in total, stack 1MB
  16. Input
  17. There can be more than one test case in the input file. 
  18. The first line has T, the number of test cases. 
  19. Then T cases are provided in the following lines. (1≤T≤30)
  20. The first line of each test case contains the size of the array N(1≤N≤200,000).
  21. The next line contains N integers in the array.
  22. The integers are between 1 and 10,000,000, inclusive, and are all different. 
  23. - Scores : The maximum scores out of your submissions. (Full score: 100)
  24.   The group of test cases are as follows. When you report the right answers for all test cases in a group, you get its partial score. 
  25.   Group 1 (17 points): 1≤N≤2,000
  26.   Group 2 (83 points): No further restrictions
  27. Output
  28. For each test case, you are supposed to write its answer to the standard output in the same order as the input.
  29. For the C-th test case, “Case #C” should be printed out in the first line.
  30. The following line should contain the number of elements satisfying the Pivot condition.
  31. Input/Output Sample
  32. Input
  33. 2
  34. 2
  35. 3 1
  36. 4
  37. 1 2 3 4
  38. Output
  39. Case #1
  40. 0
  41. Case #2
  42. 4
  43. */
  44.  
  45. /*
  46. You should use the standard input/output
  47.  
  48. in order to receive a score properly.
  49.  
  50. Do not use file input and output
  51.  
  52. Please be very careful. 
  53. */
  54.  
  55. #include <stdio.h>
  56. #include <stdlib.h>
  57.  
  58. int Answer;
  59.  
  60. int main(void)
  61. {
  62. 	int T, test_case;
  63. 	/*
  64. 	   The freopen function below opens input.txt file in read only mode, and afterward,
  65. 	   the program will read from input.txt file instead of standard(keyboard) input.
  66. 	   To test your program, you may save input data in input.txt file,
  67. 	   and use freopen function to read from the file when using scanf function.
  68. 	   You may remove the comment symbols(//) in the below statement and use it.
  69. 	   But before submission, you must remove the freopen function or rewrite comment symbols(//).
  70. 	 */
  71. 	//freopen("D:/input.txt", "r", stdin);
  72.  
  73. 	/*
  74. 	   If you remove the statement below, your program's output may not be recorded
  75. 	   when your program is terminated after the time limit.
  76. 	   For safety, please use setbuf(stdout, NULL); statement.
  77. 	 */
  78. 	setbuf(stdout, NULL);
  79.  
  80. 	scanf("%d", &T);
  81. 	for(test_case = 0; test_case < T; test_case++)
  82. 	{
  83.  
  84. 		/////////////////////////////////////////////////////////////////////////////////////////////
  85. 		Answer = 0;
  86. 		int N, max_left;
  87. 		scanf("%d",&N);
  88. 		int* a= (int*) malloc (N*sizeof(int));
  89. 	    int* min_right= (int*) malloc (N*sizeof(int));
  90.  
  91. 		if (N == 1) {Answer = 1;}
  92. 		else {
  93.  
  94. 			for(int i=0; i <= N-1; i++){
  95. 				scanf("%d", a+i);
  96. 			}
  97.  
  98. 			max_left=a[0]; min_right[N-1]=a[N-1];
  99.  
  100. 			for(int i=N-2; i>=1; i--){
  101. 				min_right[i]=(a[i] < min_right[i+1]) ? a[i] : min_right[i+1];
  102. 			}
  103.  
  104. 			if (a[0] < min_right[1]) Answer++;
  105.  
  106. 			for(int i=1; i < N-1; i++){
  107. 				if (max_left < a[i]) {
  108. 					if (a[i] < min_right[i+1]) Answer++;
  109. 					max_left = a[i];
  110. 				}
  111. 			}
  112.  
  113. 			if (max_left < a[N-1]) Answer++;
  114. 		}
  115. 		free(a); free(min_right);
  116. 		/////////////////////////////////////////////////////////////////////////////////////////////
  117.  
  118.         		// Print the answer to standard output(screen).
  119.  
  120. 		printf("Case #%d\n", test_case+1);
  121. 	        	printf("%d\n", Answer);
  122.  
  123. 	}
  124.  
  125. 	return 0;//Your program should return 0 on normal termination.
  126. }
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
2
2
3 1
4
1 2 3 4
stdout
copy 
Case #1
0
Case #2
4
https://ideone.com/ztuXza
language:
C (gcc 8.3)
created:
6 years ago
visibility:
public

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!