import java.util.*; public class NonogramsTom { // 1 means black // -1 means white public static boolean feasible(int[] S, int k, int[] A) { int n = A.length; // M[i][j] := can blocks [0, j-1] satisfy cells [0, i-1]? // M[i][j] = M[i-1][j] if A[i-1] = -1 // = M[i-S[j-1]-1][j-1] if A[i-1] = 1 // = either or if A[i-1] = 0 // M[0][0] = true // M[i][0] = true so long as no 1's in first i entries of A // M[0][j] = false for j > 0 // false if first index < 0 // if the last cell (i-1) is white, M[i][j] = M[i-1][j] // if the last cell (i-1) is black, then the last S[j-1] cells must be not white: // i-S[j-1], ..., i-1 // furthermore, either (a) this was the first block and everything before is not black // // or (b) the previous cell (i-S[j-1]-1) must be not black and M[i-S[j-1]-1][j-1] // (i >= S[j-1]) && noWhite[i-S[j-1]][i-1] && (((j == 1) && noBlack[0][i-S[j-1]-1] ) || ((i> S[j-1]) && noBlack[i-S[j-1]-1][i-S[j-1]-1] && M[i-S[j-1]-1][j-1])) boolean[][] M = new boolean[n+1][k+1]; M[0][0] = true; boolean[][] noWhite = new boolean[n][n]; boolean[][] noBlack = new boolean[n][n]; for(int i = 0; i < n; i++) { noWhite[i][i] = (A[i] >= 0); noBlack[i][i] = (A[i] <= 0); for (int j = i+1; j < n; j++) { noWhite[i][j] = noWhite[i][j-1] && (A[j] >= 0); noBlack[i][j] = noBlack[i][j-1] && (A[j] <= 0); } } for(int i = 1; i <= n; i++) { if (A[i-1] == 1) break; M[i][0] = true; } for(int j = 1; j <= k; j++) { for(int i = 1; i <= n; i++) { boolean a = M[i-1][j]; //boolean b = (i == S[j-1] && j == 1 && noWhite[0][i-1]) || ((i>S[j-1]) && M[i-S[j-1]-1][j-1] && noWhite[i-S[j-1]][i-1]); boolean b = (i >= S[j-1]) && noWhite[i-S[j-1]][i-1] && (((j == 1) && (i == S[j-1] || noBlack[0][i-S[j-1]-1] )) || ((i> S[j-1]) && noBlack[i-S[j-1]-1][i-S[j-1]-1] && M[i-S[j-1]-1][j-1])); M[i][j] = (a && A[i-1] <= 0) || (b && A[i-1] >= 0); } } /* for(int j = 0; j <= k; j++) { System.out.print("First "+j+" blocks: "); for(int i = 1; i <= n; i++) { System.out.print(M[i][j]?"O":"."); } System.out.println(); }*/ return M[n][k]; } public static boolean checkForUpdates(int[] S, int k, int[] A) { boolean changed = false; int n = A.length; for(int i = 0; i < n; i++) { if (A[i] == 0) { A[i] = 1; if (!feasible(S,k,A)) { A[i] = -1; changed = true; } else { A[i] = -1; if (!feasible(S, k, A)) { A[i] = 1; changed = true; } else { A[i] = 0; } } } } return changed; } public static void printBoard(int[][] b) { int n = b.length; int m = b[0].length; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { char c = '?'; if (b[i][j] == 1) c = 'X'; if (b[i][j] == -1) c = '.'; System.out.print(c); } System.out.println(); } } public static void printRandom(int n, int m) { System.out.println(n+" "+m); boolean[][] board = new boolean[n][m]; Random rand = new Random(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { board[i][j] = rand.nextBoolean() || rand.nextBoolean(); System.out.print(board[i][j]?"X":"."); } System.out.println(); } System.out.println(); for(int i = 0; i < n; i++) { int count = 0; int current = 0; int[] counts = new int[m]; for(int j = 0; j < m; j++) { if (board[i][j]) { current++; } else { if (current > 0) { counts[count] = current; current = 0; count++; } } } if (current > 0) { counts[count] = current; current = 0; count++; } System.out.print(count); for(int j = 0; j < count; j++) System.out.print(" "+counts[j]); System.out.println(); } for(int j = 0; j < m; j++) { int count = 0; int current = 0; int[] counts = new int[n]; for(int i = 0; i < n; i++) { if (board[i][j]) { current++; } else { if (current > 0) { counts[count] = current; current = 0; count++; } } } if (current > 0) { counts[count] = current; current = 0; count++; } System.out.print(count); for(int i = 0; i < count; i++) System.out.print(" "+counts[i]); System.out.println(); } } public static void main(String[] args) { //printRandom(50,50); Scanner input = new Scanner(System.in); int n = input.nextInt(); // rows int m = input.nextInt(); // cols int c = 1; // while (n > 0) { int[] rl = new int[n]; int[] cl = new int[m]; int[][] rows = new int[n][m]; int[][] cols = new int[m][n]; for (int i = 0; i < n; i++) { rl[i] = input.nextInt(); for (int j = 0; j < rl[i]; j++) { rows[i][j] = input.nextInt(); } } for (int i = 0; i < m; i++) { cl[i] = input.nextInt(); for (int j = 0; j < cl[i]; j++) { cols[i][j] = input.nextInt(); } } int[][] board = new int[n][m]; boolean changed = true; while(changed) { //printBoard(board); changed = false; for(int row = 0; row < n; row++) { // update rows int[] R = new int[m]; for(int i = 0; i < m; i++) { R[i] = board[row][i]; } if (checkForUpdates(rows[row],rl[row],R)) { changed = true; for(int i = 0; i < m; i++) { board[row][i] = R[i]; } } } for(int col = 0; col < m; col++) { // update cols int[] C = new int[n]; for(int i = 0; i < n; i++) { C[i] = board[i][col]; } if (checkForUpdates(cols[col],cl[col],C)) { changed = true; for(int i = 0; i < n; i++) { board[i][col] = C[i]; } } } } // System.out.println("Case " + c + ":"); printBoard(board); c++; // n = input.nextInt(); // m = input.nextInt(); // } input.close(); } }