#include #define REP(i, n) for (int i = 0; (i) < int(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i)) #define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= int(m); -- (i)) #define ALL(x) begin(x), end(x) #define dump(x) cerr << #x " = " << x << endl #define unittest_name_helper(counter) unittest_ ## counter #define unittest_name(counter) unittest_name_helper(counter) #define unittest __attribute__((constructor)) void unittest_name(__COUNTER__) () using ll = long long; using namespace std; template using reversed_priority_queue = priority_queue, greater >; template inline void chmax(T & a, T const & b) { a = max(a, b); } template inline void chmin(T & a, T const & b) { a = min(a, b); } template auto vectors(X x, T a) { return vector(x, a); } template auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector(x, cont); } template ostream & operator << (ostream & out, vector const & xs) { REP (i, int(xs.size()) - 1) out << xs[i] << ' '; if (not xs.empty()) out << xs.back(); return out; } constexpr int N = 60; constexpr int K = 500; constexpr int MAX_L = 25; constexpr int N2 = N * N; int count_black(int y, int x, bool is_vertical, int len, bitset const & a) { int cnt = 0; REP (i, len) { int ny = y + (is_vertical ? i : 0); int nx = x + (is_vertical ? 0 : i); cnt += a[ny * N + nx]; } return cnt; } void apply_rect(int y, int x, bool is_vertical, int len, bitset & a) { REP (i, len) { int ny = y + (is_vertical ? i : 0); int nx = x + (is_vertical ? 0 : i); auto && p = a[ny * N + nx]; p = not p; } } array, K> solve_greedy(array const & l, bitset & a) { array, N + 1> lookup; REP (i, K) lookup[l[i]].push_back(i); array, K> result; REP_R (len, N + 1) { for (int i : lookup[len]) { int highscore = -1; REP (y, N) REP (x, N) REP (is_vertical, 2) { if ( is_vertical and y + len > N) continue; if (not is_vertical and x + len > N) continue; int score = count_black(y, x, is_vertical, l[i], a); if (highscore < score) { highscore = score; result[i] = make_tuple(y, x, is_vertical); } } assert (highscore != -1); int y, x; bool is_vertical; tie(y, x, is_vertical) = result[i]; apply_rect(y, x, is_vertical, l[i], a); } } return result; } array, K> solve(array const & l, bitset a) { const auto TLE = chrono::microseconds(1000 * 1000 - 50 * 1000); chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now() + TLE; default_random_engine gen; array, K> result = solve_greedy(l, a); array, K> rects = result; int highscore = a.count(); int score = highscore; int iteration = 0; double temperature = 1.0; for (; ; iteration ++) { if (iteration % 100 == 0) { temperature = (clock_end - chrono::high_resolution_clock::now()).count() / (double)TLE.count(); if (temperature < 0) break; } int i = uniform_int_distribution(0, K - 1)(gen); bool is_vertical1 = bernoulli_distribution(0.5)(gen); int y1 = uniform_int_distribution(0, (N - 1) - (is_vertical1 ? l[i] : 0))(gen); int x1 = uniform_int_distribution(0, (N - 1) - (is_vertical1 ? 0 : l[i]))(gen); int y, x; bool is_vertical; tie(y, x, is_vertical) = rects[i]; apply_rect(y, x, is_vertical, l[i], a); int black = count_black(y, x, is_vertical, l[i], a); int black1 = count_black(y1, x1, is_vertical1, l[i], a); int delta = black1 - black; if (black <= black1 or bernoulli_distribution(0.01 * exp(delta) / temperature)(gen)) { rects[i] = make_tuple(y1, x1, is_vertical1); score -= l[i] - 2 * black; apply_rect(y1, x1, is_vertical1, l[i], a); score += l[i] - 2 * black1; if (score < highscore) { highscore = score; result = rects; cerr << "black = " << highscore << " / " << N2 << endl; } } else { apply_rect(y, x, is_vertical, l[i], a); } } cerr << "iteration = " << iteration << endl; cerr << "black = " << highscore << " / " << N2 << endl; return result; } int main() { // input { int n; cin >> n; assert (n == N); } { int k; cin >> k; assert (k == K); } array l; REP (i, K) cin >> l[i]; bitset a; REP (y, N) REP (x, N) { char c; cin >> c; a[y * N + x] = c - '0'; } // solve array, K> result = solve(l, a); // output REP (i, K) { int y, x; bool is_vertical; tie(y, x, is_vertical) = result[i]; int ny = y + (is_vertical ? l[i] - 1 : 0); int nx = x + (is_vertical ? 0 : l[i] - 1); cout << y + 1 << ' ' << x + 1 << ' ' << ny + 1 << ' ' << nx + 1 << endl; } return 0; }