Advertisement
Guest User

Untitled

a guest
Feb 12th, 2016
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.40 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5. #include <string.h>
  6. #include <limits.h>
  7.  
  8. int max(int x, int y)
  9. {
  10. return x <= y ? y : x;
  11. }
  12.  
  13. int min(int x, int y)
  14. {
  15. return x <= y ? x : y;
  16. }
  17.  
  18. int ints_get(int *a)
  19. {
  20. int result = 0;
  21. int x;
  22. while (scanf("%d", &x) != EOF)
  23. a[result++] = x;
  24. return result;
  25. }
  26.  
  27. int ints_get_while_not(int *a, int z)
  28. {
  29. int result = 0;
  30. int x;
  31. while (scanf("%d", &x) != EOF && x != z)
  32. a[result++] = x;
  33. return result;
  34. }
  35.  
  36. int ints_get_two(int *a, int *b)
  37. {
  38. int result = 0;
  39. int x, y;
  40. while (scanf("%d%d", &x, &y) != EOF)
  41. {
  42. a[result] = x;
  43. b[result] = y;
  44. result++;
  45. }
  46. return result;
  47. }
  48.  
  49. int ints_init(int x, int n, int *a)
  50. {
  51. int result = 0;
  52. for (int i = 0; i < n; i++)
  53. a[result++] = x;
  54. return result;
  55. }
  56.  
  57. int ints_id(int n, int *a)
  58. {
  59. int result = 0;
  60. for (int i = 0; i < n; i++)
  61. a[result++] = i;
  62. return result;
  63. }
  64.  
  65. int ints_count(const int *a, int n, int x)
  66. {
  67. int result = 0;
  68. for (int i = 0; i < n; i++)
  69. if (a[i] == x)
  70. result++;
  71. return result;
  72. }
  73.  
  74. int ints_sum(const int *a, int n)
  75. {
  76. int result = 0;
  77. for (int i = 0; i < n; i++)
  78. result += a[i];
  79. return result;
  80. }
  81.  
  82. int ints_find(const int *a, int n, int x)
  83. {
  84. for (int i = 0; i < n; i++)
  85. if (a[i] == x)
  86. return i;
  87. return -1;
  88. }
  89.  
  90. int ints_max(const int *a, int n)
  91. {
  92. int result = INT_MIN;
  93. for (int i = 0; i < n; i++)
  94. if (result < a[i])
  95. result = a[i];
  96. return result;
  97. }
  98.  
  99. int ints_min(const int *a, int n)
  100. {
  101. int result = INT_MAX;
  102. for (int i = 0; i < n; i++)
  103. if (result > a[i])
  104. result = a[i];
  105. return result;
  106. }
  107.  
  108. int ints_argmax(const int *a, int n)
  109. {
  110. int result = -1;
  111. int max = INT_MIN;
  112. for (int i = 0; i < n; i++)
  113. if (max < a[i])
  114. {
  115. max = a[i];
  116. result = i;
  117. }
  118. return result;
  119. }
  120.  
  121. int ints_argsmax(const int *a, int n, int *b)
  122. {
  123. int result = 0;
  124. int max = INT_MIN;
  125. for (int i = 0; i < n; i++)
  126. {
  127. if (max < a[i])
  128. {
  129. max = a[i];
  130. result = 0;
  131. }
  132. if (max <= a[i])
  133. b[result++] = i;
  134. }
  135. return result;
  136. }
  137.  
  138. void ints_println_basic(const int *a, int n)
  139. {
  140. if (n > 0)
  141. {
  142. printf("%d", a[0]);
  143. for (int i = 1; i < n; i++) // i = 1
  144. printf(" %d", a[i]);
  145. }
  146. printf("\n");
  147. }
  148.  
  149. void ints_println_basic_two(const int *a, const int *b, int n)
  150. {
  151. assert(n > 0);
  152. for (int i = 0; i < n; i++)
  153. printf("%d %d\n", a[i], b[i]);
  154. }
  155.  
  156. void ints_print(int *a, int n, char *separator)
  157. {
  158. if (n > 0)
  159. {
  160. printf("%d", a[0]);
  161. for (int i = 1; i < n; i++) // i = 1
  162. printf("%s%d", separator, a[i]);
  163. }
  164. }
  165.  
  166. void ints_println(int *a, int n, char *separator)
  167. {
  168. ints_print(a, n, separator);
  169. printf("\n");
  170. }
  171.  
  172. int *ints_new (int n)
  173. {
  174. return (int *) malloc (n * sizeof(int));
  175. }
  176.  
  177. //---------------------
  178.  
  179. int ints_is_sorted(int *a, int n)
  180. {
  181. for (int i = 1; i < n; i++)
  182. if (a[i-1] > a[i])
  183. return 0;
  184. return 1;
  185. }
  186.  
  187. int ints_rank(const int *a, int n, int x)
  188. {
  189. int result = 0;
  190. while (n > 0)
  191. {
  192. int m = n / 2;
  193. if (x <= a[m])
  194. n = m;
  195. else
  196. {
  197. result += m+1;
  198. a += m+1;
  199. n -= m+1;
  200. }
  201. }
  202. return result;
  203. }
  204.  
  205. int ints_bfind(const int *a, int n, int x)
  206. {
  207. int r = ints_rank(a, n, x);
  208. return r < n && a[r] == x ? r : -1;
  209. }
  210.  
  211. int ints_bfind_classic(const int *a, int n, int x)
  212. {
  213. int i = 0;
  214. int j = n-1;
  215. while (i <= j)
  216. {
  217. int m = i + (j-i) / 2;
  218. if (x < a[m])
  219. j = m-1;
  220. else if (x > a[m])
  221. i = m+1;
  222. else
  223. return m;
  224. }
  225. return -1;
  226. }
  227.  
  228. //-------------------
  229.  
  230. void ints_exchange(int *a, int x, int y)
  231. {
  232. int m = a[x];
  233. a[x] = a[y];
  234. a[y] = m;
  235. }
  236.  
  237. void ints_sort_last(int *a, int n)
  238. {
  239. int i = n-1;
  240. while (i > 0 && a[i-1] > a[i])
  241. {
  242. ints_exchange(a, i-1, i);
  243. i--;
  244. }
  245. }
  246.  
  247. int ints_insert(int *a, int n, int x)
  248. {
  249. int result = n;
  250. a[result++] = x;
  251. ints_sort_last(a, result);
  252. return result;
  253. }
  254.  
  255. void ints_isort(int *a, int n)
  256. {
  257. for (int i = 2; i <= n; i++)
  258. ints_sort_last(a, i);
  259. }
  260.  
  261. int ints_copy(const int *a, int n, int *b)
  262. {
  263. if (n < 0)
  264. n = 0;
  265. memmove(b, a, n * sizeof(int)); // Note: 3rd arg is unsigned.
  266. return n;
  267. }
  268.  
  269. int ints_merge(const int *a, int n, const int *b, int m, int *c)
  270. {
  271. int result = 0;
  272. int i = 0;
  273. int j = 0;
  274. while (i < n && j < m)
  275. if (a[i] <= b[j])
  276. c[result++] = a[i++];
  277. else
  278. c[result++] = b[j++];
  279. result += ints_copy(a + i, n - i, c+result);
  280. result += ints_copy(b + j, m - j, c+result);
  281. return result;
  282. }
  283.  
  284. void ints_msort_i(int *a, int n, int *b)
  285. {
  286. if (n > 1)
  287. {
  288. int m = n / 2;
  289. ints_msort_i(a, m, b);
  290. ints_msort_i(a+m, n-m, b);
  291. ints_merge(a, m, a+m, n-m, b);
  292. ints_copy(b, n, a);
  293. }
  294. }
  295.  
  296. void ints_msort(int *a, int n)
  297. {
  298. int *b = ints_new(n);
  299. ints_msort_i(a, n, b);
  300. }
  301.  
  302. // -----------------
  303.  
  304. int get_rising_group (int *a, int n)
  305. {
  306. int x=0;
  307. while ((x<=n)&&(a[x]<= a[x+1]))
  308. x++;
  309. return x+1;
  310. }
  311.  
  312. void tending (int *a, int n)
  313. {
  314. int result [100000];
  315. int k=0;
  316. int x=0;
  317. int msize=0;
  318. while (x<n)
  319. {
  320. k=get_rising_group (a+x, n);
  321. result[k-1]=result[k-1]+1;
  322. x=x+k;
  323. if (k>msize)
  324. msize=k;
  325. }
  326. ints_println_basic(result, msize);
  327. }
  328.  
  329.  
  330.  
  331.  
  332. int main()
  333. {
  334. int data[100000];
  335. int n= ints_get(data);
  336. tending (data, n);
  337. return 0;
  338. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement