fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. using CandiesJar = vector<int>;
  8.  
  9. static inline void ExtendUnqueRange(vector<bool>& usedFlavors,
  10.                                     CandiesJar::const_iterator& rangeEnd,
  11.                                     const CandiesJar::const_iterator& jarEnd)
  12. {
  13.     while (rangeEnd != jarEnd && !usedFlavors[*rangeEnd])
  14.     {
  15.         usedFlavors[*rangeEnd] = true;
  16.         ++rangeEnd;
  17.     }
  18. }
  19.  
  20. static inline void CollapseUniqueRangeToValue(vector<bool>& usedFlavors,
  21.                                               CandiesJar::const_iterator& rangeStart,
  22.                                               CandiesJar::value_type removeValue)
  23. {
  24.     while (*rangeStart != removeValue)
  25.     {
  26.         usedFlavors[*rangeStart] = false;
  27.         ++rangeStart;
  28.     }
  29. }
  30.  
  31. static inline auto CountPossibleSubranges(const CandiesJar::const_iterator& start,
  32.          const CandiesJar::const_iterator& stop) -> uint64_t
  33. {
  34.     auto len = static_cast<uint64_t>(distance(start, stop));
  35.     return len * (len + 1) / 2;
  36. }
  37.  
  38. auto CountSeriesWithUniqueItems(const CandiesJar& candies, int m) -> uint64_t
  39. {
  40.     auto result = uint64_t(0);
  41.     auto usedFlavors = vector<bool>(m, false);
  42.  
  43.     auto start = begin(candies);
  44.     auto stop = start;
  45.  
  46.     auto oldStop = stop;
  47.     ExtendUnqueRange(usedFlavors, stop, end(candies));
  48.  
  49.     while (stop != end(candies))
  50.     {
  51.         result += CountPossibleSubranges(start, stop) - CountPossibleSubranges(start, oldStop);
  52.  
  53.         CollapseUniqueRangeToValue(usedFlavors, start, *stop);
  54.         oldStop = stop;
  55.  
  56.         // here start and stop are pointing to same flavor
  57.         ++start; // remove flavor form beginning
  58.         ++stop; // add flavor to end
  59.  
  60.         ExtendUnqueRange(usedFlavors, stop, end(candies));
  61.     }    
  62.     result += CountPossibleSubranges(start, stop) - CountPossibleSubranges(start, oldStop);
  63.  
  64.     return result;
  65. }
  66.  
  67. int main() {
  68.     ios::sync_with_stdio(false);
  69.     cin.tie(nullptr);
  70.  
  71.     int n, m;
  72.     unsigned long long expected;
  73.     auto pass = 0;
  74.     auto fail = 0;
  75.     while (cin >> n >> m >> expected)
  76.     {
  77.         CandiesJar candies;
  78.         candies.reserve(n);
  79.         for (int i=0; i<n; ++i)
  80.         {
  81.             int c;
  82.             cin >> c;
  83.             candies.push_back(c-1);
  84.         }
  85.         auto result = CountSeriesWithUniqueItems(candies, m);
  86.         if (expected != result)
  87.         {
  88.             ++fail;
  89.             for (auto x : candies)
  90.             {
  91.                 cout << x << ", ";
  92.             }
  93.             cout << "\nExpected: " << expected << "\nActual  : " << result << '\n' << endl;
  94.         } else {
  95.             ++pass;
  96.         }
  97.     }
  98.     cout << "Pass: " << pass << " fail: " << fail <<endl;
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
5 3 10
1 2 3 2 3
5 3 9
1 3 2 2 3
5 3 12
1 2 3 1 2
5 5 15
1 2 3 4 5
5 1 5
1 1 1 1 1
9 8 41
1 2 3 4 5 1 6 7 8
stdout
copy 
Pass: 6 fail: 0
https://ideone.com/1QI9aq
SMAKOLYKI https://m...content-available-to-author-only...u.pl/c/konkurs-podstaw-algorytmiki/p/sma/
4programmers
https://4...content-available-to-author-only...s.net/Forum/C_i_C /283655-zadanie_smakolyki_c_ilosc_roznoelementowych_niezerowych_podciagow_w_danym_ciagu
language:
C++14 (gcc 8.3)
created:
7 years 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!