fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5. #include <functional>
  6. #include <random>
  7.  
  8. constexpr int SrcSize = 1000000;
  9. constexpr int NQueries = 100000;
  10.  
  11. using src_vec_t = std::vector<int>;
  12. using index_vec_t = std::vector<int>;
  13. using weight_vec_t = std::vector<int>;
  14. using pair_vec_t = std::vector<std::pair<int, int>>;
  15. using index_map_t = std::map<int, index_vec_t>;
  16. using interval_t = std::pair<int, int>;
  17. using interval_vec_t = std::vector<interval_t>;
  18. using small_map_t = std::vector<std::pair<int, int>>;
  19. using query_vec_t = std::vector<small_map_t>;
  20.  
  21. constexpr int None = -1;
  22. constexpr int Junk = -2;
  23.  
  24. src_vec_t generate_e()
  25. { // good query length = 3
  26.     src_vec_t src;
  27.     std::random_device rd;
  28.     std::default_random_engine eng{rd()};
  29.     auto exp = std::bind(std::exponential_distribution<>{0.4}, eng);
  30.  
  31.     for (int i = 0; i < SrcSize; ++i)
  32.     {
  33.         int x = exp();
  34.         src.push_back(x);
  35.         //std::cout << x << ' ';
  36.     }
  37.  
  38.     return src;
  39. }
  40.  
  41. src_vec_t generate_ep()
  42. { // good query length = 500
  43.     src_vec_t src;
  44.     std::random_device rd;
  45.     std::default_random_engine eng{rd()};
  46.     auto exp = std::bind(std::exponential_distribution<>{0.4}, eng);
  47.     auto poisson = std::bind(std::poisson_distribution<int>{100}, eng);
  48.  
  49.     while (int(src.size()) < SrcSize)
  50.     {
  51.         int x = exp();
  52.         int n = poisson();
  53.  
  54.         for (int i = 0; i < n; ++i)
  55.         {
  56.             src.push_back(x);
  57.             //std::cout << x << ' ';
  58.         }
  59.     }
  60.  
  61.     return src;
  62. }
  63.  
  64. src_vec_t generate()
  65. {
  66.     //return generate_e();
  67.     return generate_ep();
  68. }
  69.  
  70. int trivial(const src_vec_t& src, interval_t qi)
  71. {
  72.     int count = 0;
  73.     int majorityElement = 0; // will be assigned before use for valid args
  74.  
  75.     for (int i = qi.first; i <= qi.second; ++i)
  76.     {
  77.         if (count == 0)
  78.             majorityElement = src[i];
  79.  
  80.         if (src[i] == majorityElement) 
  81.            ++count;
  82.         else 
  83.            --count;
  84.     }
  85.  
  86.     count = 0;
  87.     for (int i = qi.first; i <= qi.second; ++i)
  88.     {
  89.         if (src[i] == majorityElement)
  90.                 count++;
  91.     }
  92.  
  93.     if (2 * count > qi.second + 1 - qi.first)
  94.         return majorityElement;
  95.     else
  96.         return None;
  97. }
  98.  
  99. index_map_t sort_ind(const src_vec_t& src)
  100. {
  101.     int ind = 0;
  102.     index_map_t im;
  103.  
  104.     for (auto x: src)
  105.         im[x].push_back(ind++);
  106.  
  107.     return im;
  108. }
  109.  
  110. weight_vec_t get_weights(const index_vec_t& indexes)
  111. {
  112.     weight_vec_t weights;
  113.  
  114.     for (int i = 0; i != int(indexes.size()); ++i)
  115.         weights.push_back(2 * i - indexes[i]);
  116.  
  117.     return weights;
  118. }
  119.  
  120. pair_vec_t get_prefix(const index_vec_t& indexes, const weight_vec_t& weights)
  121. {
  122.     pair_vec_t prefix;
  123.  
  124.     for (int i = 0; i != int(indexes.size()); ++i)
  125.         if (prefix.empty() || weights[i] < prefix.back().second)
  126.             prefix.emplace_back(indexes[i], weights[i]);
  127.  
  128.     return prefix;
  129. }
  130.  
  131. pair_vec_t get_suffix(const index_vec_t& indexes, const weight_vec_t& weights)
  132. {
  133.     pair_vec_t suffix;
  134.  
  135.     for (int i = indexes.size() - 1; i >= 0; --i)
  136.         if (suffix.empty() || weights[i] > suffix.back().second)
  137.             suffix.emplace_back(indexes[i], weights[i]);
  138.  
  139.     std::reverse(suffix.begin(), suffix.end());
  140.     return suffix;
  141. }
  142.  
  143. interval_vec_t get_intervals(const pair_vec_t& prefix, const pair_vec_t& suffix)
  144. {
  145.     interval_vec_t intervals;
  146.     int prev_suffix_index = 0; // will be assigned before use for correct args
  147.     int prev_suffix_weight = 0; // same assumptions
  148.  
  149.     for (int ind_pref = 0, ind_suff = 0; ind_pref != int(prefix.size());)
  150.     {
  151.         auto i_pref = prefix[ind_pref].first;
  152.         auto w_pref = prefix[ind_pref].second;
  153.  
  154.         if (ind_suff != int(suffix.size()))
  155.         {
  156.             auto i_suff = suffix[ind_suff].first;
  157.             auto w_suff = suffix[ind_suff].second;
  158.  
  159.             if (w_pref <= w_suff)
  160.             {
  161.                 auto beg = std::max(0, i_pref + w_pref - w_suff);
  162.  
  163.                 if (i_pref < i_suff)
  164.                     intervals.emplace_back(beg, i_suff + 1);
  165.  
  166.                 if (w_pref == w_suff)
  167.                     ++ind_pref;
  168.  
  169.                 ++ind_suff;
  170.                 prev_suffix_index = i_suff;
  171.                 prev_suffix_weight = w_suff;
  172.                 continue;
  173.             }
  174.         }
  175.  
  176.         // ind_suff out of bounds or w_pref > w_suff:
  177.         auto end = prev_suffix_index + prev_suffix_weight - w_pref + 1;
  178.         // end may be out-of-bounds; that's OK if overflow is not possible
  179.         intervals.emplace_back(i_pref, end);
  180.         ++ind_pref;
  181.     }
  182.  
  183.     return intervals;
  184. }
  185.  
  186. interval_vec_t merge(const interval_vec_t& from)
  187. {
  188.     using endpoints_t = std::vector<std::pair<int, bool>>;
  189.     endpoints_t ep(2 * from.size());
  190.  
  191.     std::transform(from.begin(), from.end(), ep.begin(),
  192.                    [](interval_t x){ return std::make_pair(x.first, true); });
  193.  
  194.     std::transform(from.begin(), from.end(), ep.begin() + from.size(),
  195.                    [](interval_t x){ return std::make_pair(x.second, false); });
  196.  
  197.     std::sort(ep.begin(), ep.end());
  198.  
  199.     interval_vec_t to;
  200.     int start; // will be assigned before use for correct args
  201.     int overlaps = 0;
  202.  
  203.     for (auto& x: ep)
  204.     {
  205.         if (x.second) // begin
  206.         {
  207.             if (overlaps++ == 0)
  208.                 start = x.first;
  209.         }
  210.         else // end
  211.         {
  212.             if (--overlaps == 0)
  213.                 to.emplace_back(start, x.first);
  214.         }
  215.     }
  216.  
  217.     return to;
  218. }
  219.  
  220. interval_vec_t get_intervals(const index_vec_t& indexes)
  221. {
  222.     auto weights = get_weights(indexes);
  223.     auto prefix = get_prefix(indexes, weights);
  224.     auto suffix = get_suffix(indexes, weights);
  225.     auto intervals = get_intervals(prefix, suffix);
  226.     return merge(intervals);
  227. }
  228.  
  229. void update_qv(
  230.     query_vec_t& qv,
  231.     int value,
  232.     const interval_vec_t& intervals,
  233.     const index_vec_t& iv)
  234. {
  235.     int iv_ind = 0;
  236.     int qv_ind = 0;
  237.     int accum = 0;
  238.  
  239.     for (auto& interval: intervals)
  240.     {
  241.         int i_begin = interval.first;
  242.         int i_end = std::min<int>(interval.second, qv.size() - 1);
  243.  
  244.         while (iv[iv_ind] < i_begin)
  245.         {
  246.             ++accum;
  247.             ++iv_ind;
  248.         }
  249.  
  250.         qv_ind = std::max(qv_ind, i_begin);
  251.  
  252.         while (qv_ind <= i_end)
  253.         {
  254.             qv[qv_ind].emplace_back(value, accum);
  255.  
  256.             if (iv[iv_ind] == qv_ind)
  257.             {
  258.                 ++accum;
  259.                 ++iv_ind;
  260.             }
  261.  
  262.             ++qv_ind;
  263.         }
  264.     }
  265. }
  266.  
  267. void print_preprocess_stat(const index_map_t& im, const query_vec_t& qv)
  268. {
  269.     double sum_coverage = 0.;
  270.     int max_coverage = 0;
  271.  
  272.     for (auto& x: qv)
  273.     {
  274.         sum_coverage += x.size();
  275.         max_coverage = std::max<int>(max_coverage, x.size());
  276.     }
  277.  
  278.     std::cout << "             size = " << qv.size() - 1 << '\n';
  279.     std::cout << "           values = " << im.size() << '\n';
  280.     std::cout << "     max coverage = " << max_coverage << '\n';
  281.     std::cout << "     avg coverage = " << sum_coverage / qv.size() << '\n';
  282. }
  283.  
  284. query_vec_t preprocess(const src_vec_t& src)
  285. {
  286.     query_vec_t qv(src.size() + 1);
  287.     auto im = sort_ind(src);
  288.  
  289.     for (auto& val: im)
  290.     {
  291.         auto intervals = get_intervals(val.second);
  292.         update_qv(qv, val.first, intervals, val.second);
  293.     }
  294.  
  295.     print_preprocess_stat(im, qv);
  296.     return qv;
  297. }
  298.  
  299. int do_query(const src_vec_t& src, const query_vec_t& qv, interval_t qi)
  300. {
  301.     if (qi.first == qi.second)
  302.         return src[qi.first];
  303.  
  304.     auto b = qv[qi.first].begin();
  305.     auto e = qv[qi.second + 1].begin();
  306.  
  307.     while (b != qv[qi.first].end() && e != qv[qi.second + 1].end())
  308.     {
  309.         if (b->first < e->first)
  310.         {
  311.             ++b;
  312.         }
  313.         else if (e->first < b->first)
  314.         {
  315.             ++e;
  316.         }
  317.         else // if (e->first == b->first)
  318.         {
  319.             // hope this doesn't overflow
  320.             if (2 * (e->second - b->second) > qi.second + 1 - qi.first)
  321.                 return b->first;
  322.  
  323.             ++b;
  324.             ++e;
  325.         }
  326.     }
  327.  
  328.     return None;
  329. }
  330.  
  331. int main()
  332. {
  333.     std::random_device rd;
  334.     std::default_random_engine eng{rd()};
  335.     auto poisson = std::bind(std::poisson_distribution<int>{500}, eng);
  336.     int majority = 0;
  337.     int nonzero = 0;
  338.     int failed = 0;
  339.  
  340.     auto src = generate();
  341.     auto qv = preprocess(src);
  342.  
  343.     for (int i = 0; i < NQueries; ++i)
  344.     {
  345.         int size = poisson();
  346.         auto ud = std::uniform_int_distribution<int>(0, src.size() - size - 1);
  347.         int start = ud(eng);
  348.         int stop = start + size;
  349.         auto res1 = do_query(src, qv, {start, stop});
  350.         auto res2 = trivial(src, {start, stop});
  351.         //std::cout << size << ": " << res1 << ' ' << res2 << '\n';
  352.  
  353.         if (res2 != res1)
  354.             ++failed;
  355.  
  356.         if (res2 != None)
  357.         {
  358.             ++majority;
  359.  
  360.             if (res2 != 0)
  361.                 ++nonzero;
  362.         }
  363.     }
  364.  
  365.     std::cout << "majority elements = " << 100. * majority / NQueries << "%\n";
  366.     std::cout << " nonzero elements = " << 100. * nonzero / NQueries << "%\n";
  367.     std::cout << "          queries = " << NQueries << '\n';
  368.     std::cout << "           failed = " << failed << '\n';
  369.  
  370.     return 0;
  371. }
  372.  
Success #stdin #stdout 0.81s 37632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
             size = 1000017
           values = 21
     max coverage = 6
     avg coverage = 2.73128
majority elements = 31.564%
 nonzero elements = 11.685%
          queries = 100000
           failed = 0
https://ideone.com/FLSDhe
language:
C++14 (gcc 8.3)
created:
10 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!