Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <assert.h>
- #include <bitset>
- #include <chrono>
- #include <cstring>
- #include <functional>
- #include <iostream>
- #include <istream>
- #include <map>
- #include <numeric>
- #include <ostream>
- #include <queue>
- #include <set>
- #include <stack>
- #include <string>
- #include <unordered_map>
- #include <unordered_set>
- #include <vector>
- #include <random>
- #define endl '\n'
- using namespace std;
- const int maxn = 200100;
- int a[maxn], n;
- int P[maxn], S[maxn];
- void my_swap(int i)
- {
- swap(a[i], a[i + 1]);
- P[i] = min(P[i - 1], a[i]);
- P[i + 1] = min(P[i], a[i + 1]);
- S[i + 1] = min(S[i + 2], a[i + 1]);
- S[i] = min(S[i + 1], a[i]);
- }
- int query_mex(int i, int j)
- {
- return min(P[i - 1], S[j + 1]);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- mt19937 gen;
- int q, s, k;
- cin >> n >> q >> k >> s;
- gen.seed(s);
- int last = 0;
- P[0] = S[n + 1] = n;
- for (int i = 1; i <= n; ++i)
- {
- cin >> a[i];
- }
- for (int i = 1; i <= n; ++i)
- {
- P[i] = min(P[i - 1], a[i]);
- }
- for (int i = n; i; --i)
- {
- S[i] = min(S[i + 1], a[i]);
- }
- while (q--)
- {
- int op = gen() % k;
- int i = (gen() + last) % n;
- if (!op && i)
- {
- my_swap(i);
- }
- else
- {
- int j = gen() % n;
- if (i > j)
- swap(i, j);
- last ^= query_mex(i + 1, j + 1);
- }
- }
- cout << last << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement