/* DO NOT CHANGE THIS FILE! */

/** A BitMatrix represents an NxN matrix of 1's and 0's in which all
 *  1's occur before all 0's in each row.
 * @author P. N. Hilfinger
 */
public class BitMatrix {

    /** An N x N BitMatrix, initially all 0s. */
    public BitMatrix(int n) {
        firstZero = new int[n];
    }

    /** Returns n, where THIS is an nxn BitMatrix. */
    public int size() {
        return firstZero.length;
    }

    /** Returns the contents of (ROW, COL) in THIS BitMatrix. */
    public int get(int row, int col) {
        if (col >= firstZero[row])  {
            return 0;
        } else {
            return 1;
        }
    }

    /** Set the contents of (ROW, COL) in THIS to VAL, treating all
     *  non-zero VALs as if they were 1.  Modify other values in the
     *  same as little as possible to guarantee that all 1's still come
     *  before all 0's.
     * NOTE: Your solution should not use this method.  It's here so
     *  that you (and we) can build BitMatrices for testing purposes. */
    public void set(int row, int col, int val) {
        if (val != 0) {
            val = 1;
        }

        if (val == 0) {
            firstZero[row] = Math.min(firstZero[row], col);
        } else {
            firstZero[row] = Math.max(firstZero[row], col + 1);
        }
    }

    /** firstZero[k] is the index of the first 0 in row k. */
    private int[] firstZero;
}