fork download
  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
stdin
Standard input is empty
stdout
             size = 1000017
           values = 21
     max coverage = 6
     avg coverage = 2.73128
majority elements = 31.564%
 nonzero elements = 11.685%
          queries = 100000
           failed = 0