SRM 761 500pts. SortArray
From 0-1 sorting lemma, we have an algorithm.
#include <bits/stdc++.h> using namespace std; struct SortArray { vector<int> verify(int N, vector<int> commands) { for (int i = 0; i < 1 << N; i++) { vector<int> a(N); for (int j = 0; j < N; j++) { a[j] = i >> j & 1; } for (int x : commands) { int c = 0; for (int j = 0; j < N; j++) { if (x >> j & 1) { c += !a[j]; } } for (int j = 0; j < N; j++) { if (x >> j & 1) { if (c > 0) { a[j] = 0; c--; } else { a[j] = 1; } } } } if (!is_sorted(a.begin(), a.end())) { int l = 0; int r = N - 1; vector<int> ans; for (int j = 0; j < N; j++) { if (~i >> j & 1) { ans.push_back(l++); } else { ans.push_back(r--); } } return ans; } } return {}; } };