#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define ll long long #define mp make_pair #define ins insert #define lb lower_bound #define pb push_back #define ub upper_bound #define lll __int128 #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; int main() { int w, n; cin >> w >> n; int perm[n]; for (int i = 0; i < n; ++i) { cin >> perm[i]; } if (w == 0) { cout << 3 << endl; } else { // subtask 1, 3 (19 points) // how do you do a swap? // let's say we have a, b we want to swap // 1 1 -> 1 1 -> 1 1 -> 1 1 // 0 1 -> 0 0 -> 1 0 -> 1 0 // 1 0 -> 1 0 -> 0 0 -> 0 1 // 0 0 -> 0 1 -> 0 1 -> 0 0 // subtask 4, 5 (26 points) // how do you shift? // a b c d e f -> b c d e f a // let's represent as disjoint swaps? // a b c d e f -> b a d c f e -> b c d a f e -> b c d e f a (3 * 3) // 3 * logN operations for general, is there a faster way? // a b c d -> b c d a // a b c d -> c b a d -> b c d a // a b c d e f -> c b a f e d -> b c d e f a // general algo? // for 6: // a[1] a[2] a[3] a[4] a[5] a[6] // a[3] a[2] a[1] a[6] a[5] a[4] // a[2] a[3] a[4] a[5] a[6] a[1] // for 12: // a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] // a[3] a[2] a[1] a[6] a[5] a[4] a[9] a[8] a[7] a[12] a[11] a[10] // a[2] a[3] a[4] a[5] a[6] a[1] a[8] a[9] a[10] a[11] a[12] a[7] // a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[1] // for 10: // 1 2 3 4 5 6 7 8 9 10 // 9 8 7 6 5 4 3 2 1 10 // 2 3 4 5 6 7 8 9 10 1 // OBSERVE: we can reverse everything then swap // for 16: // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 // 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16 // 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 // W = 9 solution: Done // TODO: // 1. Implement a swap routine, test with subtask 1, 3 // swap procedure: // 1 1 -> 1 1 -> 1 1 -> 1 1 // 0 1 -> 0 0 -> 1 0 -> 1 0 // 1 0 -> 1 0 -> 0 0 -> 0 1 // 0 0 -> 0 1 -> 0 1 -> 0 0 vector<int> vals(n, 0); auto swp = [&] (int x, int y) { if (w % 3 == 1 || w % 3 == 0) { if (x > y) { return vals[x] ^ !vals[y]; } else { return vals[x]; } } else { if (x < y) { return vals[x] ^ !vals[y]; } else { return vals[x]; } } }; if (w & 1) { for (int i = 0; i < n; ++i) { cin >> vals[i]; int cur; if (n == 2 && perm[0] == 0) cur = swp(i, i); else cur = swp(i, n - i - 1); cout << cur << endl; } } else { for (int i = n - 1; i >= 0; --i) { cin >> vals[i]; int cur; if (n == 2 && perm[0] == 0) cur = swp(i, i); else cur = swp(i, n - i - 1); cout << cur << endl; } } } return 0; }