fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // Generalized Suffix Automaton Node
  7. struct State {
  8.     int len, link;
  9.     int next[10]; // Alphabet size is 10 (digits 0-9, though 1-9 are used)
  10. };
  11.  
  12. const int MAX_STATES = 6000005; // Safe upper limit for sum of lengths
  13. State st[MAX_STATES];
  14. int sz = 0;
  15.  
  16. void sam_init() {
  17.     st[0].len = 0;
  18.     st[0].link = -1;
  19.     for (int i = 0; i < 10; ++i) st[0].next[i] = 0;
  20.     sz = 0;
  21. }
  22.  
  23. // Function to extend the Generalized Suffix Automaton correctly across multiple strings
  24. int sam_extend(int last, int c) {
  25.     if (st[last].next[c]) {
  26.         int q = st[last].next[c];
  27.         if (st[q].len == st[last].len + 1) {
  28.             return q;
  29.         } else {
  30.             int clone = ++sz;
  31.             st[clone].len = st[last].len + 1;
  32.             for (int i = 0; i < 10; ++i) st[clone].next[i] = st[q].next[i];
  33.             st[clone].link = st[q].link;
  34.             while (last != -1 && st[last].next[c] == q) {
  35.                 st[last].next[c] = clone;
  36.                 last = st[last].link;
  37.             }
  38.             st[q].link = clone;
  39.             return clone;
  40.         }
  41.     }
  42.  
  43.     int cur = ++sz;
  44.     st[cur].len = st[last].len + 1;
  45.     for (int i = 0; i < 10; ++i) st[cur].next[i] = 0;
  46.  
  47.     int p = last;
  48.     while (p != -1 && !st[p].next[c]) {
  49.         st[p].next[c] = cur;
  50.         p = st[p].link;
  51.     }
  52.     if (p == -1) {
  53.         st[cur].link = 0;
  54.     } else {
  55.         int q = st[p].next[c];
  56.         if (st[p].len + 1 == st[q].len) {
  57.             st[cur].link = q;
  58.         } else {
  59.             int clone = ++sz;
  60.             st[clone].len = st[p].len + 1;
  61.             for (int i = 0; i < 10; ++i) st[clone].next[i] = st[q].next[i];
  62.             st[clone].link = st[q].link;
  63.             while (p != -1 && st[p].next[c] == q) {
  64.                 st[p].next[c] = clone;
  65.                 p = st[p].link;
  66.             }
  67.             st[q].link = st[cur].link = clone;
  68.         }
  69.     }
  70.     return cur;
  71. }
  72.  
  73. int main() {
  74.     // Optimize standard I/O operations for performance
  75.     ios_base::sync_with_stdio(false);
  76.     cin.tie(NULL);
  77.  
  78.     int N;
  79.     if (!(cin >> N)) return 0;
  80.  
  81.     vector<int> A(N);
  82.     for (int i = 0; i < N; ++i) {
  83.         cin >> A[i];
  84.     }
  85.  
  86.     // Run-Length Encoding of sequence A
  87.     vector<int> V, L;
  88.     for (int i = 0; i < N; ++i) {
  89.         if (V.empty() || V.back() != A[i]) {
  90.             V.push_back(A[i]);
  91.             L.push_back(1);
  92.         } else {
  93.             L.back()++;
  94.         }
  95.     }
  96.  
  97.     int K = V.size();
  98.     vector<int> type(K);
  99.     for (int i = 0; i < K; ++i) {
  100.         if (L[i] < V[i]) type[i] = 0;       // Deficient
  101.         else if (L[i] > V[i]) type[i] = 1;  // Abundant
  102.         else type[i] = 2;                   // Perfect
  103.     }
  104.  
  105.     sam_init();
  106.  
  107.     // Condition 1: Maximal continuous sequences of Perfect blocks bounded by Abundant ones
  108.     for (int i = 0; i < K; ++i) {
  109.         if (type[i] == 2) {
  110.             int j = i;
  111.             while (j < K && type[j] == 2) j++;
  112.  
  113.             int l = i, r = j - 1;
  114.             if (l > 0 && type[l - 1] >= 1) l--;
  115.             if (r < K - 1 && type[r + 1] >= 1) r++;
  116.  
  117.             int last = 0;
  118.             for (int k = l; k <= r; ++k) {
  119.                 last = sam_extend(last, V[k]);
  120.             }
  121.             i = j - 1; // Skip the Perfect segment we just explored
  122.         }
  123.     }
  124.  
  125.     // Condition 2: Adjacent independent Abundant pairs
  126.     for (int i = 0; i < K - 1; ++i) {
  127.         if (type[i] == 1 && type[i + 1] == 1) {
  128.             int last = sam_extend(0, V[i]);
  129.             sam_extend(last, V[i + 1]);
  130.         }
  131.     }
  132.  
  133.     // Condition 3: Any valid individual block
  134.     for (int i = 0; i < K; ++i) {
  135.         if (type[i] >= 1) {
  136.             sam_extend(0, V[i]);
  137.         }
  138.     }
  139.  
  140.     // Tabulate distinct paths in the Suffix Automaton
  141.     long long distinct_sequences = 0;
  142.     for (int i = 1; i <= sz; ++i) {
  143.         distinct_sequences += (st[i].len - st[st[i].link].len);
  144.     }
  145.  
  146.     cout << distinct_sequences << "\n";
  147.  
  148.     return 0;
  149. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
23
2 2 3 3 3 1 1 1 3 3 3 1 2 2 2 1 9 1 4 4 4 4 4
stdout
copy 
14
https://ideone.com/Usp0L9
language:
C++14 (gcc 8.3)
created:
1 hour 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!