Verifier for Codeforces Round 876 (Div. 2) Problem C. Insert Zero and Invert Prefix

verify-C.cc

// Codeforces Round 876 (Div. 2) Problem C. Insert Zero and Invert Prefix
// https://codeforces.com/contest/1839/problem/C
//
// How to efficiently verify an arbitrary solution?
//
// Discussion:
// https://mirror.codeforces.com/blog/entry/116963?#comment-1034335

#include <bits/stdc++.h>

#if __has_include("dump.h")
#include "dump.h"
#else
#define DUMP(...)
#endif

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

using namespace __gnu_pbds;
using __gnu_cxx::rope;
using ordered_int_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i,a,b) for (int i = int(a), _end_##i = int(b); i < _end_##i; ++i)
#define REP(i,n) FOR(i,0,n)

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, v.size()) {
    if (i > 0) os << ' ';
    os << v[i];
  }
  return os;
}

// O(N^2) implementation that just simulates every operation.
vector<int> Reconstruct1(const vector<int> &B) {
  vector<int> A;
  for (int b : B) {
    auto it = A.begin();
    while (b-- > 0) *it++ ^= 1;
    A.insert(it, 0);
  }
  return A;
}

// O(N^2) implementation that shows the idea behind the efficient implementation.
//
// First, construct an array I that contains for each index in the final array A
// the index of the operation that caused this value to be inserted.
// i.e. if B[i] ends up at index j in the final array, then I[j] = i.
// I is necessarily a permutation of [0, 1, .. N-1].
//
// Example:
//
//  B = [0, 0, 0, 0] -> I = [3, 2, 1, 0]
//  B = [0, 1, 2, 3] -> I = [0, 1, 2, 3]
//  B = [0, 0, 2, 1] -> I = [1, 3, 0, 2]
//
// The element A[i] was flipped once for all 0s that were inserted after it and
// to the right of it. In other words, we need to count the number of indices j
// such that i < j and I[i] < I[j].
//
vector<int> Reconstruct2(const vector<int> &B) {
  int N = B.size();

  vector<int> I;
  REP(i, N) I.insert(I.begin() + B[i], i);

  vector<int> A;
  REP(i, N) {
    int flips = 0;
    FOR(j, i + 1, N) if (I[j] > I[i]) ++flips;
    A.push_back(flips & 1);
  }
  return A;
}

// Calculates the array I above, but using a rope for efficiency.
// A skip list or another datastructure that allows efficient insertion at
// random indices would also work.
vector<int> InsertionIndex1(const vector<int> &B) {
  rope<int> I;
  REP(i, B.size()) I.insert(B[i], i);
  return vector<int>(I.begin(), I.end());
}

// Similar to InsertionIndex1 but uses an ordered set instead.
vector<int> InsertionIndex2(const vector<int> &B) {
  const int N = B.size();
  ordered_int_set S;
  for (int i = 0; i < N; ++i) S.insert(i);
  vector<int> I(N, -1);
  for (int i = N - 1; i >= 0; --i) {
    auto it = S.find_by_order(B[i]);
    assert(it != S.end() && I[*it] == -1);
    I[*it] = i;
    S.erase(it);
  }
  return I;
}

// Reconstructs A using the array I from above, but using an ordered set for
// efficiency (a Fenwick tree/segment tree could also be used.)
vector<int> ReconstructFromIndex(const vector<int> &I) {
  vector<int> A(I.size());
  ordered_int_set S;
  for (int i = (int) I.size() - 1; i >= 0; --i) {
    int flips = S.size() - S.order_of_key(I[i]);
    S.insert(I[i]);
    A[i] = flips & 1;
  }
  return A;
}

// O(N log N) implementation.
vector<int> Reconstruct3(const vector<int> &B) {
  return ReconstructFromIndex(InsertionIndex2(B));
}

/* Returns `num` with only highest bit set, or 0 if num was 0. */
size_t highest_bit(size_t num) {
  if (num) num = (unsigned long long)1 << (std::numeric_limits<unsigned long long>::digits - 1 - __builtin_clzll(num));
  return num;
}

/* Converts a regular array into a Fenwick array (in linear time). */
static void fenwick_construct(std::vector<int> &a) {
  for (size_t i = 1; i < a.size(); i = 2 * i)
    for (size_t j = 2 * i - 1; j < a.size(); j += 2 * i)
      a[j] += a[j - i];
}

/* Adds `v` to the value stored at index `i`. */
static void fenwick_update(std::vector<int> &a, size_t i, int v) {
  while (i < a.size()) a[i] += v, i |= i + 1;
}

/* Calculates the sum of the first `n` elements in `a` (which are the elements
   with zero-based indices strictly less than n). */
static int fenwick_prefixsum(const std::vector<int> &a, size_t n) {
  int res = 0;
  while (n > 0) res += a[n - 1], n &= n - 1;
  return res;
}

/* Assuming all values are nonnegative, returns the least index `n` such that
   fenwick_prefixsum(a, n) > sum, or returns a.size() + 1 if there is none. */
static size_t fenwick_upperbound(const std::vector<int> &a, int sum) {
  size_t n = 0;
  for (size_t bit = highest_bit(a.size()); bit; bit >>= 1) {
    if (n + bit <= a.size() && sum >= a[n + bit - 1]) {
      sum -= a[n + bit - 1];
      n += bit;
    }
  }
  return n + (sum >= 0);
}

// O(N log N) implementation using a Fenwick tree.
vector<int> Reconstruct4(const vector<int> &B) {
  const int N = B.size();
  vector<int> A(N, -1);

  // A Fenwick array that is used as an ordered set which contains the available
  // indices in A, from 1 to N (exclusive). Initially, all positions are available.
  vector<int> available(N, 1);
  fenwick_construct(available);

  // We go through the array from back to front, since the final index and the
  // number of times a bit is flipped depends only on the bits that are inserted
  // after the i-th element, not before it.
  for (int j = N - 1; j >= 0; --j) {
    // Determine the final index where zero inserted at position B[j] ends up.
    // This is simply the i-th index in A that hasn't been assigned yet, which
    // we can find in the Fenwick array:
    int i = fenwick_upperbound(available, B[j]) - 1;
    assert(i < N);

    // Now we know the index in A, but we also need to calculate the value.
    // The total number of times this bit will be flipped is equal to the
    // number of bits that are inserted after the j-th element, and after
    // index i.
    int later_bits = N - 1 - j;
    int inserted_before = i - fenwick_prefixsum(available, i);
    int flips = later_bits - inserted_before;

    assert(A[i] == -1);
    A[i] = flips & 1;

    // Remove the index `i` from available. (This could be done earlier too.)
    fenwick_update(available, i, -1);
  }

  return A;
}

int main() {
  vector<int> B;
  for (int b; (cin >> b); ) {
    assert(0 <= b && b <= B.size());
    B.push_back(b);
  }

  if (0) {
    vector<int> A1 = Reconstruct1(B);
    vector<int> A2 = Reconstruct2(B);
    vector<int> A3 = Reconstruct3(B);
    vector<int> A4 = Reconstruct4(B);

    assert(A1 == A2);
    assert(A2 == A3);
    assert(A3 == A4);

    cout << A4 << endl;
  } else {
    cout << Reconstruct4(B) << endl;
  }
}