fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     string val;
  6.     int count;
  7. };
  8.  
  9. void burstArrayLinear(vector<string>& arr, int k) {
  10.     if (k <= 1) {
  11.         arr.clear();
  12.         return;
  13.     }
  14.  
  15.     stack<Node> s;
  16.  
  17.     for (const string& str : arr) {
  18.         // If current matches the top of stack, increase its count
  19.         if (!s.empty() && s.top().val == str) {
  20.             s.top().count++;
  21.         } else {
  22.             // Before pushing a new char, check if the current top should burst
  23.             if (!s.empty() && s.top().count >= k) {
  24.                 s.pop();
  25.                 // After popping, the NEW top might match the current string
  26.                 if (!s.empty() && s.top().val == str) {
  27.                     s.top().count++;
  28.                 } else {
  29.                     s.push({str, 1});
  30.                 }
  31.             } else {
  32.                 s.push({str, 1});
  33.             }
  34.         }
  35.     }
  36.  
  37.     // Final check for the last remaining element in stack
  38.     if (!s.empty() && s.top().count >= k) {
  39.         s.pop();
  40.     }
  41.  
  42.     // Reconstruct the array from stack
  43.     vector<string> result;
  44.     vector<Node> temp;
  45.     while (!s.empty()) {
  46.         temp.push_back(s.top());
  47.         s.pop();
  48.     }
  49.  
  50.     // Reverse to get correct order and expand counts
  51.     for (int i = temp.size() - 1; i >= 0; i--) {
  52.         for (int j = 0; j < temp[i].count; j++) {
  53.             result.push_back(temp[i].val);
  54.         }
  55.     }
  56.     arr = result;
  57. }
  58.  
  59. int main() {
  60.     int n, k;
  61.     cin >> n;
  62.     vector<string> input(n);
  63.     for (int i = 0; i < n; i++) cin >> input[i];
  64.     cin >> k;
  65.  
  66.     burstArrayLinear(input, k);
  67.  
  68.     for (const string& s : input) cout << s << endl;
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
10
a
a
b
b
b
c
c
c
a
a
3
stdout
copy 
Standard output is empty
https://ideone.com/l6C8al
language:
C++14 (gcc 8.3)
created:
21 hours 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!