Guest User

Untitled

a guest
May 10th, 2020
174
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <assert.h>
  3. #include <bitset>
  4. #include <chrono>
  5. #include <cstring>
  6. #include <functional>
  7. #include <iostream>
  8. #include <istream>
  9. #include <map>
  10. #include <numeric>
  11. #include <ostream>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <string>
  16. #include <unordered_map>
  17. #include <unordered_set>
  18. #include <vector>
  19. #include <random>
  20.  
  21. #define endl '\n'
  22.  
  23. using namespace std;
  24.  
  25. const int maxn = 200100;
  26.  
  27. int a[maxn], n;
  28.  
  29. int P[maxn], S[maxn];
  30.  
  31. void my_swap(int i)
  32. {
  33.     swap(a[i], a[i + 1]);
  34.  
  35.     P[i] = min(P[i - 1], a[i]);
  36.     P[i + 1] = min(P[i], a[i + 1]);
  37.  
  38.     S[i + 1] = min(S[i + 2], a[i + 1]);
  39.     S[i] = min(S[i + 1], a[i]);
  40. }
  41.  
  42. int query_mex(int i, int j)
  43. {
  44.     return min(P[i - 1], S[j + 1]);
  45. }
  46.  
  47. int main()
  48. {
  49.     ios_base::sync_with_stdio(0);
  50.     cin.tie(0);
  51.  
  52.     mt19937 gen;
  53.  
  54.     int q, s, k;
  55.     cin >> n >> q >> k >> s;
  56.  
  57.     gen.seed(s);
  58.  
  59.     int last = 0;
  60.  
  61.     P[0] = S[n + 1] = n;
  62.  
  63.     for (int i = 1; i <= n; ++i)
  64.     {
  65.         cin >> a[i];
  66.     }
  67.  
  68.     for (int i = 1; i <= n; ++i)
  69.     {
  70.         P[i] = min(P[i - 1], a[i]);
  71.     }
  72.  
  73.     for (int i = n; i; --i)
  74.     {
  75.         S[i] = min(S[i + 1], a[i]);
  76.     }
  77.  
  78.     while (q--)
  79.     {
  80.         int op = gen() % k;
  81.  
  82.         int i = (gen() + last) % n;
  83.  
  84.         if (!op && i)
  85.         {
  86.             my_swap(i);
  87.         }
  88.         else
  89.         {
  90.             int j = gen() % n;
  91.  
  92.             if (i > j)
  93.                 swap(i, j);
  94.  
  95.             last ^= query_mex(i + 1, j + 1);
  96.         }
  97.     }
  98.  
  99.     cout << last << endl;
  100.  
  101.     return 0;
  102. }
RAW Paste Data