Advertisement
Guest User

Untitled

a guest
Apr 19th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.16 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<string> split_string(string);
  6.  
  7.  
  8. /*
  9. window size: 7
  10. 0 1 2 3 4 5 6 7
  11. 0 1 1 2 5 7 7 9
  12. 0 -> 1
  13. 1 -> 2
  14. 2 -> 1
  15. 3 -> 0
  16. 4 -> 0
  17. 5 -> 1
  18. 7 -> 2
  19. 8 -> 0
  20. 9 -> 1
  21.  
  22. 0 2 3 4 6 7
  23. */
  24.  
  25. class CountSortedList {
  26. public:
  27. CountSortedList(int range_size)
  28. : _valueFrequency(range_size, 0) {};
  29.  
  30. void addValue(int value) {
  31. _valueFrequency.at(value) += 1;
  32. }
  33.  
  34. void removeValue(int value) {
  35. _valueFrequency.at(value) -= 1;
  36. }
  37.  
  38. int at(uint index) const {
  39. auto count = -1;
  40. cout << "index: " << index << endl;
  41. for(auto it = _valueFrequency.cbegin(); it < _valueFrequency.cend(); ++it) {
  42. cout << "it: " << *it;
  43. count += *it;
  44. cout << "count: " << count << endl;
  45. if (count >= index) {
  46. return it - _valueFrequency.cbegin();
  47. }
  48. }
  49. return -1;
  50. }
  51.  
  52. private:
  53. vector<int> _valueFrequency;
  54. };
  55.  
  56. int twiceMedian(CountSortedList const& expenditure_frequency, int window_size) {
  57. if (window_size % 2 == 1) {
  58. // 0 1 2 [3] 4 5 6
  59. int median_index = window_size / 2;
  60. auto median = expenditure_frequency.at(median_index);
  61. return 2 * median;
  62. } else { // even window size
  63. // 0 1 [2] [3] 4 5
  64. auto low_median_index = window_size / 2 - 1;
  65. auto low_median = expenditure_frequency.at(low_median_index);
  66. auto high_median_index = low_median_index + 1;
  67. auto high_median = expenditure_frequency.at(high_median_index);
  68. return low_median + high_median;
  69. }
  70. }
  71.  
  72. // Complete the activityNotifications function below.
  73. int activityNotifications(vector<int> expenditure, int window_size) {
  74. CountSortedList expenditure_frequency{201};
  75.  
  76. auto notification_count = 0;
  77. auto window_start = expenditure.begin();
  78. auto window_end = expenditure.begin() + window_size;
  79.  
  80. for (auto it = window_start; it < window_end; ++it) {
  81. expenditure_frequency.addValue(*it);
  82. }
  83.  
  84. while (window_end != expenditure.end() - 1) {
  85. auto const current_day_expenditure = window_end;
  86. auto twice_median = twiceMedian(expenditure_frequency, window_size);
  87. if (*current_day_expenditure >= twice_median) {
  88. cout << "twice median: " << twice_median << endl;
  89. cout << "window end: " << *window_end << endl;
  90. notification_count++;
  91. }
  92. expenditure_frequency.removeValue(*window_start);
  93. window_start++;
  94. window_end++;
  95. expenditure_frequency.addValue(*window_end);
  96. }
  97. return notification_count;
  98. }
  99.  
  100. int main()
  101. {
  102. ofstream fout(getenv("OUTPUT_PATH"));
  103.  
  104. string nd_temp;
  105. getline(cin, nd_temp);
  106.  
  107. vector<string> nd = split_string(nd_temp);
  108.  
  109. int n = stoi(nd[0]);
  110.  
  111. int d = stoi(nd[1]);
  112.  
  113. string expenditure_temp_temp;
  114. getline(cin, expenditure_temp_temp);
  115.  
  116. vector<string> expenditure_temp = split_string(expenditure_temp_temp);
  117.  
  118. vector<int> expenditure(n);
  119.  
  120. for (int i = 0; i < n; i++) {
  121. int expenditure_item = stoi(expenditure_temp[i]);
  122.  
  123. expenditure[i] = expenditure_item;
  124. }
  125.  
  126. int result = activityNotifications(expenditure, d);
  127.  
  128. fout << result << "\n";
  129.  
  130. fout.close();
  131.  
  132. return 0;
  133. }
  134.  
  135. vector<string> split_string(string input_string) {
  136. string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
  137. return x == y and x == ' ';
  138. });
  139.  
  140. input_string.erase(new_end, input_string.end());
  141.  
  142. while (input_string[input_string.length() - 1] == ' ') {
  143. input_string.pop_back();
  144. }
  145.  
  146. vector<string> splits;
  147. char delimiter = ' ';
  148.  
  149. size_t i = 0;
  150. size_t pos = input_string.find(delimiter);
  151.  
  152. while (pos != string::npos) {
  153. splits.push_back(input_string.substr(i, pos - i));
  154.  
  155. i = pos + 1;
  156. pos = input_string.find(delimiter, i);
  157. }
  158.  
  159. splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
  160.  
  161. return splits;
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement