Advertisement
Guest User

Untitled

a guest
Dec 13th, 2013
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:64777216")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include<iostream>
  4. #include<stdio.h>
  5. #include<algorithm>
  6. #include<vector>
  7. #include<math.h>
  8. #include<string>
  9. #include<sstream>
  10. #include<set>
  11. #include<map>
  12. #include<stack>
  13. #include<queue>
  14. #include<deque>
  15. #include<memory.h>
  16. #include<ctype.h>
  17. #include<stdio.h>
  18.  
  19. #define pb push_back
  20. #define sz(a) (int)a.size()
  21. #define bs binary_search
  22. #define np next_permutation
  23. #define mp make_pair
  24. #define all(a) a.begin(),a.end()
  25.  
  26. typedef long long ll;
  27.  
  28. using namespace std;
  29.  
  30. const double pi = 3.141592653589793238, eps = 1e-9;
  31. const ll INF = 9999999999;
  32.  
  33. int n, i, a[5000005], k, col = 0, x, j;
  34. vector<int> ans;
  35. bool used[5000005];
  36.  
  37. void prepare(string s) {
  38. #ifdef _DEBUG
  39. freopen("input.txt", "r", stdin);
  40. freopen("output.txt","w",stdout);
  41. #else
  42. if (sz(s) != 0) {
  43. freopen((s + ".in").c_str(), "r", stdin);
  44. freopen((s + ".out").c_str(), "w", stdout);
  45. }
  46. #endif
  47. }
  48.  
  49. int bin_search (int l, int r){
  50. int mid = (l + r) / 2;
  51. if (a[mid] <= x && !used[mid])
  52. return mid;
  53. else
  54. return bin_search (mid, r);
  55. }
  56.  
  57. int main()
  58. {
  59. prepare("");
  60. cin>> n;
  61. memset(used, false, sizeof used);
  62. for (i=0;i<n;i++)
  63. cin>> a[i];
  64. sort(a, a + n);
  65. reverse(a, a + n);
  66. int ind = -1;
  67. int ps;
  68. if (n % 2 == 0)
  69. ps = n / 2;
  70. else
  71. ps = n / 2 + 1;
  72. for (i=ps;i<n;i++)
  73. if (a[i] * 2 <= a[0])
  74. {
  75. ind = i;
  76. col++;
  77. break;
  78. }
  79. int pos = 0;
  80. if (ind == -1)
  81. cout<< n;
  82. else
  83. {
  84. for (i=ind+1;i<n;i++)
  85. for (j=pos+1;j<ind;j++)
  86. if (a[i] * 2 <= a[j])
  87. {
  88. col++;
  89. ind = i;
  90. pos = j;
  91. break;
  92. }
  93. cout<< n - col;
  94. }
  95. return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement