Inserting values at maximal distance from current value
Use an interval tree to store a set of intervals, where you have one interval for each chunk of contiguous 0's.  Now to figure out where to put the next 1, you need to find the longest interval in the interval tree.  You can keep track of the longest interval in the interval tree by augmenting the data structure: store in each node the length of the longest interval under that node.  Each operation can be done in $O(\log n)$ time.