Advertisement
MathQ_

Untitled

Nov 10th, 2020
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  2. #pragma GCC optimize 03
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <iterator>
  8. #include <cmath>
  9. #include <ctime>
  10. #include <vector>
  11. #include <deque>
  12. #include <queue>
  13. #include <set>
  14. #include <map>
  15. #include <stack>
  16. #include <string>
  17. #include <random>
  18. #include <numeric>
  19. #include <unordered_set>
  20.  
  21. typedef long long ll;
  22. typedef long double lb;
  23.  
  24. #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  25. #define file_in freopen("input.txt", "r", stdin);
  26. #define file_in_out freopen("knapsack.in", "r", stdin); freopen("knapsack.out", "w", stdout);
  27. #define mp make_pair
  28. #define all(x) (x).begin(), (x).end()
  29. #define fi first
  30. #define se second
  31.  
  32. using namespace std;
  33.  
  34. template<typename T>
  35. istream& operator>>(istream &in, vector<T> &v) {
  36.     for (auto &it : v) {
  37.         in >> it;
  38.     }
  39.     return in;
  40. }
  41.  
  42. template<typename T>
  43. ostream& operator<<(ostream &out, vector<T> &v) {
  44.     if (!v.empty()) {
  45.         out << v.front();
  46.         for (int i = 1; i < v.size(); ++i) {
  47.             out << " " << v[i];
  48.         }
  49.     }
  50.     return out;
  51. }
  52.  
  53. const int LOG = 24, MAXN = 16714589;
  54. //map<int, int> _log;
  55. vector<vector<int>> spt;
  56.  
  57. int rmq(int l, int r) {
  58.     //int t = _log[r - l + 1];
  59.     int t = __lg(r - l + 1);
  60.     return min(spt[l][t], spt[r - (1 << t) + 1][t]);
  61. }
  62.  
  63. int main() {
  64.     fast
  65. //  file_in
  66. //  file_in_out
  67.  
  68.     int n, m, a0, u, v;
  69.     cin >> n >> m >> a0 >> u >> v;
  70.  
  71.     /*
  72.     _log.resize(MAXN);
  73.     _log[1] = 0;
  74.     for (int i = 2; i <= MAXN; ++i) {
  75.         _log[i] = _log[i / 2] + 1;
  76.     }
  77.     */
  78.  
  79.     spt.resize(n, vector<int>(LOG + 1));
  80.     spt[0][0] = a0;
  81.     for (int i = 1; i < n; ++i) {
  82.         spt[i][0] = (23 * spt[i - 1][0] + 21563) % MAXN;
  83.     }
  84.     for (int j = 1; j <= LOG; j++) {
  85.         for (int i = 0; i + (1 << j) <= n; i++) {
  86.             spt[i][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
  87.         }
  88.     }
  89.     int ans;
  90.     for (int i = 1; i <= m; ++i) {
  91.         if (u > v) {
  92.             ans = rmq(v - 1, u - 1);
  93.         } else {
  94.             ans = rmq(u - 1, v - 1);
  95.         }
  96.         if (i == m) break;
  97.         u = ((17 * u + 751 + ans + 2 * i) % n) + 1;
  98.         v = ((13 * v + 593 + ans + 5 * i) % n) + 1;
  99.     }
  100.     cout << u << " " << v << " " << ans;
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement