Advertisement
MathQ_

Untitled

Nov 10th, 2020
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 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, MAXA = 16714589, MAXN = 1e5;
  54. int spt[LOG + 1][MAXN];
  55.  
  56. int rmq(int l, int r) {
  57.     int t = __lg(r - l + 1);
  58.     return min(spt[t][l], spt[t][r - (1 << t) + 1]);
  59. }
  60.  
  61. int main() {
  62.     fast
  63. //  file_in
  64. //  file_in_out
  65.  
  66.     int n, m, a0, u, v;
  67.     cin >> n >> m >> a0 >> u >> v;
  68.  
  69.     spt[0][0] = a0;
  70.     for (int i = 1; i < n; ++i) {
  71.         spt[0][i] = (23 * spt[0][i - 1] + 21563) % MAXA;
  72.     }
  73.     for (int j = 1; j <= LOG; j++) {
  74.         for (int i = 0; i + (1 << j) <= n; i++) {
  75.             spt[j][i] = min(spt[j - 1][i], spt[j - 1][i + (1 << (j - 1))]);
  76.         }
  77.     }
  78.     int ans;
  79.     for (int i = 1; i <= m; ++i) {
  80.         if (u > v) {
  81.             ans = rmq(v - 1, u - 1);
  82.         } else {
  83.             ans = rmq(u - 1, v - 1);
  84.         }
  85.         if (i == m) break;
  86.         u = ((17 * u + 751 + ans + 2 * i) % n) + 1;
  87.         v = ((13 * v + 593 + ans + 5 * i) % n) + 1;
  88.     }
  89.     cout << u << " " << v << " " << ans;
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement