#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; } } template array, K> solve1(array const & l, bitset & a, RandomEngine & gen) { array, N + 1> lookup; REP (i, K) lookup[l[i]].push_back(i); array priority_table; REP (z, N2) priority_table[z] = gen(); array, K> result; REP_R (len, N + 1) { for (int i : lookup[len]) { int highscore = -1, priority = 0; 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 or (highscore == score and priority < priority_table[y * N + x])) { highscore = score; priority = priority_table[y * N + x]; 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 const & a) { chrono::high_resolution_clock::time_point clock_begin = chrono::high_resolution_clock::now(); default_random_engine gen; array, K> result; int highscore = -1; int iteration = 0; for (; ; iteration ++) { chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now(); if (chrono::duration_cast(clock_end - clock_begin).count() >= 900) break; auto na = a; auto it = solve1(l, na, gen); int score = na.size() - na.count(); if (highscore < score) { highscore = score; result = it; } cerr << "score = " << score << " / " << N2 << endl; // it seems to have failed } cerr << "iteration = " << iteration << endl; cerr << "score = " << 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; }