Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<string> split_string(string);
- /*
- window size: 7
- 0 1 2 3 4 5 6 7
- 0 1 1 2 5 7 7 9
- 0 -> 1
- 1 -> 2
- 2 -> 1
- 3 -> 0
- 4 -> 0
- 5 -> 1
- 7 -> 2
- 8 -> 0
- 9 -> 1
- 0 2 3 4 6 7
- */
- class CountSortedList {
- public:
- CountSortedList(int range_size)
- : _valueFrequency(range_size, 0) {};
- void addValue(int value) {
- _valueFrequency.at(value) += 1;
- }
- void removeValue(int value) {
- _valueFrequency.at(value) -= 1;
- }
- int at(uint index) const {
- auto count = -1;
- cout << "index: " << index << endl;
- for(auto it = _valueFrequency.cbegin(); it < _valueFrequency.cend(); ++it) {
- cout << "it: " << *it;
- count += *it;
- cout << "count: " << count << endl;
- if (count >= index) {
- return it - _valueFrequency.cbegin();
- }
- }
- return -1;
- }
- private:
- vector<int> _valueFrequency;
- };
- int twiceMedian(CountSortedList const& expenditure_frequency, int window_size) {
- if (window_size % 2 == 1) {
- // 0 1 2 [3] 4 5 6
- int median_index = window_size / 2;
- auto median = expenditure_frequency.at(median_index);
- return 2 * median;
- } else { // even window size
- // 0 1 [2] [3] 4 5
- auto low_median_index = window_size / 2 - 1;
- auto low_median = expenditure_frequency.at(low_median_index);
- auto high_median_index = low_median_index + 1;
- auto high_median = expenditure_frequency.at(high_median_index);
- return low_median + high_median;
- }
- }
- // Complete the activityNotifications function below.
- int activityNotifications(vector<int> expenditure, int window_size) {
- CountSortedList expenditure_frequency{201};
- auto notification_count = 0;
- auto window_start = expenditure.begin();
- auto window_end = expenditure.begin() + window_size;
- for (auto it = window_start; it < window_end; ++it) {
- expenditure_frequency.addValue(*it);
- }
- while (window_end != expenditure.end() - 1) {
- auto const current_day_expenditure = window_end;
- auto twice_median = twiceMedian(expenditure_frequency, window_size);
- if (*current_day_expenditure >= twice_median) {
- cout << "twice median: " << twice_median << endl;
- cout << "window end: " << *window_end << endl;
- notification_count++;
- }
- expenditure_frequency.removeValue(*window_start);
- window_start++;
- window_end++;
- expenditure_frequency.addValue(*window_end);
- }
- return notification_count;
- }
- int main()
- {
- ofstream fout(getenv("OUTPUT_PATH"));
- string nd_temp;
- getline(cin, nd_temp);
- vector<string> nd = split_string(nd_temp);
- int n = stoi(nd[0]);
- int d = stoi(nd[1]);
- string expenditure_temp_temp;
- getline(cin, expenditure_temp_temp);
- vector<string> expenditure_temp = split_string(expenditure_temp_temp);
- vector<int> expenditure(n);
- for (int i = 0; i < n; i++) {
- int expenditure_item = stoi(expenditure_temp[i]);
- expenditure[i] = expenditure_item;
- }
- int result = activityNotifications(expenditure, d);
- fout << result << "\n";
- fout.close();
- return 0;
- }
- vector<string> split_string(string input_string) {
- string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
- return x == y and x == ' ';
- });
- input_string.erase(new_end, input_string.end());
- while (input_string[input_string.length() - 1] == ' ') {
- input_string.pop_back();
- }
- vector<string> splits;
- char delimiter = ' ';
- size_t i = 0;
- size_t pos = input_string.find(delimiter);
- while (pos != string::npos) {
- splits.push_back(input_string.substr(i, pos - i));
- i = pos + 1;
- pos = input_string.find(delimiter, i);
- }
- splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
- return splits;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement