fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using LL = long long;
  6. template<typename T> using V = vector<T>; 
  7. template<typename T, typename S> using P = pair<T, S>; 
  8. template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
  9. using LD = long double;
  10.  
  11. #define ALL(v) v.begin(), v.end()
  12. #define endl '\n'
  13. #define SYNC ios_base::sync_with_stdio(false); cin.tie(NULL); cerr.tie(NULL);
  14. #define REP(i, n) for(int i = 0; i < (int)n ;i++)
  15. #define REPN(i, n) for(int i = 1; i <= (int)n ; i++)
  16. #define her 	cerr << "here\n" 
  17. #define pp push_back
  18. #define fi first 
  19. #define se second
  20. #define un(x) x.erase(unique(ALL(x)), x.end())
  21.  
  22. template<typename T, typename S> void check(T & a, S & b) { if (a >= b) { a %= b; } }
  23. template<typename T>T gcd(T u, T v) { if (u == v)return u; if (u == 0)return v; if (v == 0)return u; if (~u & 1) { if (v & 1) return gcd(u >> 1, v); else return gcd(u >> 1, v >> 1) << 1; }if (~v & 1)return gcd(u, v >> 1); if (u > v)return gcd((u - v) >> 1, v); return gcd((v - u) >> 1, u); }
  24.  
  25. const int N = (int)1e5 + 10; 
  26.  
  27. #define int long long
  28.  
  29. int solve(auto & a, auto & b, int k){
  30. 	map<P<int, P<int,int>>, int> vis;
  31.  
  32. 	int n = (int)a.size(); 
  33. 	reverse(ALL(a)); 
  34. 	reverse(ALL(b));
  35.  
  36. 	priority_queue< P<int,P<int,int>> > q; 
  37. 	q.push({a[0] * b[0], {0, 0}}); 
  38. 	q.push({a[n - 1] * b[n - 1], {n - 1,  n - 1}});
  39.  
  40. 	int last = 0;
  41.  
  42. 	REPN(i, k){
  43. 		auto u = q.top(); 
  44. 		q.pop();
  45. 		if(vis[u]){
  46. 			i--;
  47. 			continue; 
  48. 		}
  49. 		vis[u] = true;
  50. 		last = u.fi; 
  51. 		int y = u.se.fi, z = u.se.se;
  52.  
  53. 		if(y + 1 < n){
  54. 			q.push({a[y + 1] * b[z], {y + 1, z}}); 
  55. 		}
  56.  
  57. 		if(z + 1 < n){
  58. 			q.push({a[y] * 1LL *  b[z + 1], {y, z + 1}}); 
  59. 		}
  60.  
  61. 		if(y - 1 >= 0){
  62. 			q.push({a[y - 1] * b[z], {y - 1, z}}); 
  63. 		}
  64.  
  65. 		if(z - 1 >= 0){
  66. 			q.push({a[y] * b[z - 1], {y, z - 1}}); 
  67. 		}
  68. 	}
  69.  
  70. 	return last;
  71. }
  72.  
  73. int a[N], b[N];
  74.  
  75. int32_t main(){
  76. 	SYNC;
  77. 	cout << fixed << setprecision(10); 
  78. 	int T; int caseno = 1; 
  79. 	cin >> T; 
  80.  
  81. 	while(T--){
  82. 		cout << "Case #" << caseno++ << ": ";
  83. 		//m.clear(); 
  84. 		int n, k, l1, l2,  c, d, e1, e2, f; 
  85. 		cin >> n >> k >> l1 >> l2 >> c >> d >> e1 >> e2 >> f; 
  86.  
  87. 		V<int> x(n), y(n), r(n, 0), s(n, 0); 
  88. 		x[0] = a[0] = l1; y[0] = b[0] = l2; 
  89.  
  90. 		REPN(i, n - 1){
  91. 			x[i] = (x[i - 1] * c + d * y[i - 1] + e1) % f; 
  92. 			y[i] = (y[i - 1] * c + d * x[i - 1] + e2) % f; 
  93. 			r[i] = (r[i - 1] * c + d * s[i - 1] + e1) % 2; 
  94. 			s[i] = (r[i - 1] * d + c * s[i - 1] + e2) % 2; 
  95. 			a[i] = (r[i] & 1 ? - x[i] : x[i]); 
  96. 			b[i] = (s[i] & 1 ? - y[i] : y[i]); 
  97. 		}
  98.  
  99. 		V<int> f1, f2;
  100.  
  101. 		REP(i, n){
  102. 			int sum = 0; 
  103. 			for(int j = i; j < n; j++){
  104. 				sum += a[j];
  105. 				f1.pp(sum); 
  106. 			}
  107. 		}
  108.  
  109. 		REP(i, n){
  110. 			int sum = 0; 
  111. 			for(int j = i; j < n; j++){
  112. 				sum += b[j];
  113. 				f2.pp(sum);   
  114. 			}
  115. 		}
  116.  
  117. 		sort(ALL(f1)); sort(ALL(f2));
  118.  
  119. 		cout << solve(f1, f2, k) << endl; 
  120. 		cerr << "Caseno: " << caseno - 1 << " done\n";  
  121. 	}
  122.  
  123.     cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n'; 
  124.     return 0; 
  125. }
Success #stdin #stdout #stderr 0.48s 26848KB
comments (?)
stdin
copy 
20
2 3 1 1 1 1 1 1 5
1 1 2 2 2 2 2 2 5
10 1 624 483 111 919 537 524 697
10 3025 532 655 892 185 807 5 311
10 10 970 187 640 680 648 936 184
10 3000 160 249 791 182 530 799 427
10 1 518 856 845 1 431 172 999
10 3025 40 119 982 496 304 145 965
10 10 408 551 310 536 528 262 982
10 3000 838 293 346 61 936 5 983
200 1 319 835 442 955 696 848 471
200 100000 872 383 577 432 115 539 976
200 50000 966 681 25 941 76 819 999
200 10 487 220 678 634 296 440 537
200 99990 886 207 469 223 168 837 972
200 50000 117 354 0 0 682 766 942
200 98347 337 619 265 0 556 833 968
200 98785 967 602 0 872 246 620 975
200 50052 113 948 890 0 488 912 958
200 50068 142 245 0 830 950 173 999
stdout
copy 
Case #1: 6
Case #2: 4
Case #3: 2341318
Case #4: -495126
Case #5: 1481742
Case #6: -604126
Case #7: 7479360
Case #8: -10039491
Case #9: 24221600
Case #10: -1296165
Case #11: 2456798088
Case #12: 23325777
Case #13: 30277832
Case #14: 2962436256
Case #15: 4764816
Case #16: 17741033388
Case #17: 131285880
Case #18: 7291265589
Case #19: 7750747348
Case #20: -51984
stderr
copy 
Caseno: 1 done
Caseno: 2 done
Caseno: 3 done
Caseno: 4 done
Caseno: 5 done
Caseno: 6 done
Caseno: 7 done
Caseno: 8 done
Caseno: 9 done
Caseno: 10 done
Caseno: 11 done
Caseno: 12 done
Caseno: 13 done
Caseno: 14 done
Caseno: 15 done
Caseno: 16 done
Caseno: 17 done
Caseno: 18 done
Caseno: 19 done
Caseno: 20 done
Time elapsed :490.158 ms
https://ideone.com/wQ2k6C
language:
C++14 (gcc 8.3)
created:
7 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!