fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int log2(int n) {
  5.     n--;
  6.     int c = 0;
  7.     while (n > 0) {
  8.         c++;
  9.         n /= 2;
  10.     }
  11.     return c;
  12. }
  13.  
  14. int pow2(int n){
  15. 	int t = 1; 
  16. 	for (int i = 0; i < n; i++){
  17. 		t *= 2;
  18. 	}
  19. 	return t;
  20. }
  21.  
  22. int main() {
  23. 	int n, m, a1;
  24. 	cin >> n >> m >> a1;
  25. 	int table[n][log2(n) + 2];
  26. 	table[0][0] = a1;
  27.     for (int i = 1; i < n; i++) {
  28.         table[0][i] = (23 * table[i][0] + 21563) % 16714589;
  29.     }
  30.     for (int j = 1; pow2(j) < n; j++) {
  31.         int i = 0;
  32.         while (i + pow2(j - 1) < n) {
  33.             table[i][j] = min(table[i][j - 1], table[i + pow2(j - 1)][j - 1]);
  34.             i++;
  35.         }
  36.     }
  37.     int logs2[n + 1];
  38.     int pows2[log2(n) + 2];
  39.     for (int i = 0; i < log2(n) + 2; i++) {
  40.         pows2[i] = pow2(i);
  41.     }
  42.     for (int i = 1; i < n + 1; i++) {
  43.         logs2[i] = log2(i - 1)  + 1;
  44.     }
  45.     int l, r;
  46.     cin >> l >> r;
  47.     int ans;
  48.     int k;
  49.     for (int i = 0; i < m; i++) {
  50.         k = logs2[abs(r - l)];
  51.         if (l <= r) {
  52.             ans = min(table[l - 1][k], table[r - pows2[k]][k]);
  53.         } else {
  54.             ans = min(table[r - 1][k], table[l - pows2[k]][k]);
  55.         }
  56.         if (i == m - 1) {
  57.             cout << l << r << ans;
  58.             return 0;
  59.         }
  60.         l = (17 * l + ans + 751 + 2 * (i + 1)) % n + 1;
  61.         r = (13 * r + ans + 593 + 5 * (i + 1)) % n + 1;
  62.     }
  63. 	return 0;
  64. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
10 8 12345
3 9
stdout
copy 
1-510
https://ideone.com/CJYtwY
language:
C++14 (gcc 8.3)
created:
5 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!