fork download
copy 
  1. #include <functional>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <ostream>
  6. #include <string>
  7.  
  8. using namespace std;
  9.  
  10. // _____________________[ recursive stable group ]___________________________ //
  11.  
  12. // stable merge of adjacent groups
  13. template<typename BidirectionalIterator>
  14. void merge_groups(BidirectionalIterator first,BidirectionalIterator middle,BidirectionalIterator last)
  15. {
  16.     typedef reverse_iterator<BidirectionalIterator> ReverseIterator;
  17.     BidirectionalIterator i=middle,current,sub_last,next_to_same;
  18.     while(i != last)
  19.     {
  20.         current = i++;
  21.         sub_last=find(i,last,*current);
  22.         if(sub_last!=last)
  23.             i = sub_last;
  24.         next_to_same = find(ReverseIterator(current),ReverseIterator(first),*current).base();
  25.         if(next_to_same!=first)
  26.            rotate(next_to_same,current,i);
  27.     }
  28. }
  29.  
  30. template<typename BidirectionalIterator>
  31. void stable_group(BidirectionalIterator first,BidirectionalIterator last)
  32. {
  33.     if(first!=last)
  34.     {
  35.         BidirectionalIterator middle=first;
  36.         typename iterator_traits<BidirectionalIterator>::difference_type range_size = distance(first,last);
  37.         if(range_size>2)
  38.         {
  39.             advance(middle,range_size/2);
  40.             stable_group(first,middle);
  41.             stable_group(middle,last);
  42.             merge_groups(first,middle,last);
  43.         }
  44.     }
  45. }
  46.  
  47. // __________________________________________________________________________ //
  48.  
  49. template<typename BidirectionalIterator>
  50. void group_gold(BidirectionalIterator first,BidirectionalIterator last)
  51. {
  52.     typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
  53.     while(first!=last)
  54.         first = stable_partition(first, last, bind1st(equal_to<value_type>(),*first));
  55. }
  56.  
  57. template<typename Range>
  58. void test_with_gold(const Range &s)
  59. {
  60.     Range p = s;
  61.     do
  62.     {
  63.         next_permutation(begin(p),end(p));
  64.         auto gold = p, recursive = p;
  65.         group_gold(begin(gold),end(gold));
  66.         stable_group(begin(recursive),end(recursive));
  67.         if(gold!=recursive)
  68.         {
  69.             cout << "Error, gold and recursive result differs" << endl;
  70.             cout << "Gold=" << gold << endl;
  71.             cout << "Recursive=" << recursive << endl;
  72.         }
  73.     }while(p!=s);
  74. }
  75.  
  76. int main()
  77. {
  78.     string tests[] =
  79.     {
  80.         "vvabcbbcc",
  81.         "asdfrrafdsr",
  82.         "abcdefgijkl",
  83.         "010101010101",
  84.         "totobobolol"
  85.     };
  86.     for(auto &&s : tests)
  87.     {
  88.         test_with_gold(s);
  89.         stable_group(begin(s),end(s));
  90.         cout << s << endl;
  91.     }
  92. }
Time limit exceeded #stdin #stdout 15s 3036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
vvabbbccc
aassddffrrr
https://ideone.com/eBFUTM
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
secret

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!