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 {};
  }
};