#include #define REP(i,a,b) for(int i=a;i> lraw; int l[666], lrr[666]; int lsum[66][66], lsum_tmp[66][66]; int usum[66][66], usum_tmp[66][66]; int N, K; int max_diff = -INF; vector> max_placement; void calc_xlsum(int i) { for (int j = N - 1; j >= 0; j--) { lsum[i][j] = (a[i][j] ? 1 : -1) + (j < N - 1 ? lsum[i][j + 1] : 0); } } void calc_yusum(int j) { for (int i = N - 1; i >= 0; i--) { usum[i][j] = (a[i][j] ? 1 : -1) + (i < N - 1 ? usum[i + 1][j] : 0); } } tuple get_max_xcand(int L) { int mx = -INF; int idx_i = -1, idx_j = -1; rep(i, N) rep(j, N - L + 1) { int cand = lsum[i][j] - ( j + L < N ? lsum[i][j + L] : 0 ); if (mx < cand) { mx = cand; idx_i = i, idx_j = j; } } return make_tuple(mx, idx_i, idx_j, idx_i, idx_j + L - 1); } tuple get_max_ycand(int L) { int mx = -INF; int idx_i = -1, idx_j = -1; rep(i, N - L + 1) rep(j, N) { int cand = usum[i][j] - ( i + L < N ? usum[i + L][j] : 0 ); if (mx < cand) { mx = cand; idx_i = i, idx_j = j; } } return make_tuple(mx, idx_i, idx_j, idx_i + L - 1, idx_j); } void solve() { int raw = 0; rep(i, N) rep(j, N) raw += !a[i][j]; vector> vec; int ret = raw; rep(k, K) { auto xcand = get_max_xcand(l[k]); auto ycand = get_max_ycand(l[k]); auto selected = max(xcand, ycand); int mx; int top, left, bottom, right; tie(mx, top, left, bottom, right) = selected; //* ret += mx; //*/ vec.emplace_back(top, left, bottom, right); if (left == right) { REP(i, top, bottom + 1) a[i][left] ^= 1; calc_yusum(left); } if (top == bottom) { REP(j, left, right + 1) a[top][j] ^= 1; calc_xlsum(top); } /* DBG("-------------------\n"); DBG("k (/ K) = %d / %d\n", k, K); rep(i, N) { rep(j, N) { if (a[i][j]) { DBG("\x1b[40m%3d\x1b[49m", a[i][j]); } else { DBG("\x1b[47m%3d\x1b[49m", a[i][j]); } } DBG("\n"); } DBG("===================\n"); PAUSE //*/ } int diff = ret - raw; /* DBG("ret = %d\n", ret); DBG("diff = %d\n", diff); PAUSE //*/ if (max_diff < diff) { max_diff = diff; int k = 0; max_placement.clear(); max_placement.resize(K); for (auto e: vec) { max_placement[lraw[k++].second] = e; } } } int main() { cin >> N >> K; rep(i, K) { int l; cin >> l; lraw.emplace_back(l, i); lrr[i] = l; } rep(i, N) { string s; cin >> s; rep(j, N) a[i][j] = a_tmp[i][j] = s[j] - '0'; } rep(i, N) { calc_xlsum(i); calc_yusum(i); rep(j, N) lsum_tmp[i][j] = lsum[i][j], usum_tmp[i][j] = usum[i][j]; } std::random_device rdev{}; std::mt19937 mt(rdev()); // k [1 - 100] 区切りでシャッフルする for (int pt = 1; pt < min(K, 11); pt++) { sort(lraw.rbegin(), lraw.rend()); for (int k = 0; ; k++) { if (k * pt >= K) break; int last = (k + 1) * pt; if (last > K) last = K; std::shuffle(lraw.begin() + k * pt, lraw.begin() + last, mt); } /* DBG("\npartition: %d\n", pt); for (auto e: lraw) { DBG("%d ", e.first); } DBG("\n"); //*/ rep(i, K) l[i] = lraw[i].first; /* DBG("-------------------\n"); rep(i, N) { rep(j, N) { DBG("%3d", a[i][j]); } DBG("\n"); } DBG("===================\n"); //*/ solve(); rep(i, N) rep(j, N) a[i][j] = a_tmp[i][j], lsum[i][j] = lsum_tmp[i][j]; } int i = 0; for (auto e: max_placement) { int x, y, z, w; tie(x, y, z, w) = e; printf("%d %d %d %d\n", x + 1, y + 1, z + 1, w + 1); // assert((x == z && y + lrr[i] - 1 == w) || (y == w && x + lrr[i] - 1 == z)); i++; } DBG("MAX = %d\n", max_diff); }