#include #include #include #include #include #include #include #include #include #include #include #include #include #include using ll = long long; enum : int { M = (int)1e9 + 7 }; enum : ll { MLL = (ll)1e18L + 9 }; using namespace std; #ifdef LOCAL #include"rprint2.hpp" #include"debug_deque.hpp" #define vector DebugDeque #else #define FUNC(name) template void name(T&&...){ } FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde); #endif template istream& operator >> (istream& in, pair& p){ in >> p.first >> p.second; return in; } template istream& operator >> (istream& in, vector& v){ for(auto& e : v){ in >> e; } return in; } #define LIMIT 0.95 mt19937 mt; timeval start; double elapsed(){ timeval now; gettimeofday(&now, nullptr); return (now.tv_sec - start.tv_sec) + (now.tv_usec - start.tv_usec) / 1e6; } struct Ans { char a, b, c, d; Ans() = default; Ans(int a, int b, int c, int d): a(a), b(b), c(c), d(d) {} friend ostream& operator << (ostream& out, Ans& e) { return out << e.a + 1 << ' ' << e.b + 1 << ' ' << e.c + 1 << ' ' << e.d + 1; } bool operator == (const Ans& e) const { // return *(int*)(this) == *(int*)(&e); return a == e.a && b == e.b && c == e.c && d == e.d; } bool operator < (const Ans&) const { return false; } }; int main(){ gettimeofday(&start, nullptr); cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; vector ls(k); cin >> ls; vector as(n); cin >> as; for(auto& a : as){ for(auto& e : a){ e -= '0'; } } auto as0 = as; auto calc = [&](){ int num = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ num += as[i][j]; } } return num; }; int score0 = calc(); vector ans(k); // vector> ps(k); // for(int i = 0; i < k; i++){ // ps[i] = {ls[i], i}; // } // sort(ps.rbegin(), ps.rend()); // for(auto p : ps){ // int i = p.second; auto rev = [](auto& e){ e = !e; }; auto put = [&](Ans a){ int ret = 0; for(int y = a.a; y <= a.c; y++){ for(int x = a.b; x <= a.d; x++){ rev(as[y][x]); ret += as[y][x] * 2 - 1; } } return ret; }; auto findBestFast = [&](int l){ pair ret(-1, {}); for(int y = 0; y < n; y++){ pair cand(0, Ans{y, 0, y, l - 1}); for(int j = 0; j < l; j++){ cand.first += as[y][j]; } ret = max(ret, cand); for(int x = 1; x < n - l + 1; x++){ cand.first -= as[y][x - 1]; cand.first += as[y][x + l - 1]; cand.second.b++; cand.second.d++; ret = max(ret, cand); } } for(int x = 0; x < n; x++){ pair cand(0, Ans{0, x, l - 1, x}); for(int j = 0; j < l; j++){ cand.first += as[j][x]; } for(int y = 1; y < n - l + 1; y++){ cand.first -= as[y - 1][x]; cand.first += as[y + l - 1][x]; cand.second.a++; cand.second.c++; ret = max(ret, cand); } } return ret; }; auto findBest = [&](int l){ pair ret(-1, {}); for(int y = 0; y < n; y++){ for(int x = 0; x < n - l; x++){ pair cand(0, Ans{y, x, y, x + l - 1}); for(int j = 0; j < l; j++){ cand.first += as[y][x + j] * 2; cand.first += l > 2 && !as[y][x + j] && y && as[y - 1][x + j] && y + 1 < n && as[y + 1][x + j]; } ret = max(ret, cand); } } for(int y = 0; y < n - l; y++){ for(int x = 0; x < n; x++){ pair cand(0, Ans{y, x, y + l - 1, x}); for(int j = 0; j < l; j++){ cand.first += as[y + j][x] * 2; cand.first += l > 2 && !as[y + j][x] && x && as[y + j][x - 1] && x + 1 < n && as[y + j][x + 1]; } ret = max(ret, cand); } } return ret; }; auto findGood = [&](int l){ pair ra(-1, {}), rb(-1, {}); // vector> rets(2, pair(-1, {})); for(int y = 0; y < n; y++){ pair cand(0, Ans{y, 0, y, l - 1}); for(int j = 0; j < l; j++){ cand.first += as[y][j]; } ra = cand; for(int x = 1; x < n - l + 1; x++){ cand.first -= as[y][x - 1]; cand.first += as[y][x + l - 1]; cand.second.b++; cand.second.d++; if(rb < cand){ rb = cand; if(ra < rb){ swap(ra, rb); } } } } for(int x = 0; x < n; x++){ pair cand(0, Ans{0, x, l - 1, x}); for(int j = 0; j < l; j++){ cand.first += as[j][x]; } if(rb < cand){ rb = cand; if(ra < rb){ swap(ra, rb); } } for(int y = 1; y < n - l + 1; y++){ cand.first -= as[y - 1][x]; cand.first += as[y + l - 1][x]; cand.second.a++; cand.second.c++; if(rb < cand){ rb = cand; if(ra < rb){ swap(ra, rb); } } } } return mt() & 1 ? ra : rb; // return rets[mt() % 2]; }; // for(int i = 0; i < k; i++){ // put(ans[i] = findBest(ls[i]).second); // } // printde(score0 - calc()); int maxi = 0; auto as1 = as; auto ans1 = ans; vector is, is2, is3; int thre = 7, thre2 = 2; for(int i = 0; i < k; i++){ (ls[i] > thre ? is : ls[i] > thre2 ? is2 : is3).push_back(i); } // vector is(k); iota(is.begin(), is.end(), 0); for(int _ = 0; _ < 10; _++){ int c2 = 0; as = as0; for(auto i : is){ auto p = findBestFast(ls[i]); // auto p = findBest(ls[i]); // c2 += p.first * 2 - ls[i] < -6; // if(p.first * 2 - ls[i] < 1 && (ls[i] == 25 || ls[i] == 23)){ // p.second = {0, 0, 0, ls[i] - 1}; // c2++; // } // if(p.first * 2 - ls[i] < -6){ // p.second = {0, 0, 0, ls[i] - 1}; // // printde(ls[i]); // } put(ans[i] = p.second); } int cand = score0 - calc(); if(maxi < cand){ maxi = cand; ans1 = ans; as1 = as; } printde(cand); shuffle(is.begin(), is.end(), mt); printde(c2); } as = as1; ans = ans1; int cnt = 0; double d; while((d = elapsed()) < LIMIT * 0.7){ for(int _ = 0; _ < 100; _++){ // for(elapsed() < LIMIT){ for(int i = 0; i < 100; i++){ cnt++; int i = is[mt() % is.size()]; auto& a = ans[i]; int diff = put(a); auto a2 = findGood(ls[i]).second; // a = findBest(ls[i]).second; diff += put(a2); // static const double startT = 10, endT = 0.01; // double temp = startT + (endT - startT) * min(1.0, elapsed() / LIMIT); // if(exp(diff / temp) * (1ull << 32) > mt()){ // if(diff > 1){ if(diff > (d < LIMIT * 0.3)){ put(a2); put(a); continue; }else{ a = a2; } if(a.a == a.c){ if(a.d + 1 < n && as[a.a][a.b] && as[a.a][a.d + 1]){ rev(as[a.a][a.b]); rev(as[a.a][a.d + 1]); a.b++; a.d++; } if(a.b && as[a.a][a.b - 1] && as[a.a][a.d]){ rev(as[a.a][a.b - 1]); rev(as[a.a][a.d]); a.b--; a.d--; } } if(a.b == a.d){ if(a.c + 1 < n && as[a.a][a.b] && as[a.c + 1][a.b]){ rev(as[a.a][a.b]); rev(as[a.c + 1][a.b]); a.a++; a.c++; } if(a.a && as[a.a - 1][a.b] && as[a.c][a.b]){ rev(as[a.a - 1][a.b]); rev(as[a.c][a.b]); a.a--; a.c--; } } } } printde(cnt); // vector> rs; // for(int i = 0; i < k; i++){ // int cnt = 0; // for(int y = ans[i].a; y <= ans[i].c; y++){ // for(int x = ans[i].b; x <= ans[i].d; x++){ // cnt += as[y][x]; // } // } // rs.emplace_back(1. * cnt / ls[i], i); // } // sort(rs.rbegin(), rs.rend()); // for(int i = 0; i < 10; i++){ // printe(rs[i].first, ls[rs[i].first]); // } int score = score0 - calc(); printde(score); // vector> ps; // for(auto i : is2){ // ps.emplace_back(ls[i], i); // } // sort(ps.rbegin(), ps.rend()); // for(auto& p : ps){ // put(ans[p.second] = findBest(p.first).second); // } // for(auto i : is2){ // put(ans[i] = findBest(ls[i]).second); // } // score = score0 - calc(); // printde(score); as0 = as; maxi = 0; for(int _ = 0; _ < 10; _++){ as = as0; for(auto i : is2){ put(ans[i] = findBest(ls[i]).second); } int cand = score0 - calc(); if(maxi < cand){ maxi = cand; ans1 = ans; as1 = as; } printde(cand); shuffle(is2.begin(), is2.end(), mt); } as = as1; ans = ans1; while(elapsed() < LIMIT){ for(int _ = 0; _ < 100; _++){ int i = mt() % k; if(ans[i] == Ans()){ continue; } // if(ls[i] <= thre2){ continue; } auto& a = ans[i]; put(a); a = findBest(ls[i]).second; put(a); if(a.a == a.c){ if(a.d + 1 < n && as[a.a][a.b] && as[a.a][a.d + 1]){ rev(as[a.a][a.b]); rev(as[a.a][a.d + 1]); a.b++; a.d++; } if(a.b && as[a.a][a.b - 1] && as[a.a][a.d]){ rev(as[a.a][a.b - 1]); rev(as[a.a][a.d]); a.b--; a.d--; } } if(a.b == a.d){ if(a.c + 1 < n && as[a.a][a.b] && as[a.c + 1][a.b]){ rev(as[a.a][a.b]); rev(as[a.c + 1][a.b]); a.a++; a.c++; } if(a.a && as[a.a - 1][a.b] && as[a.c][a.b]){ rev(as[a.a - 1][a.b]); rev(as[a.c][a.b]); a.a--; a.c--; } } } } score = score0 - calc(); printde(score); vector> ps; for(auto i : is3){ ps.emplace_back(ls[i], i); } sort(ps.rbegin(), ps.rend()); // sort(ps.begin(), ps.end()); for(auto& p : ps){ int i = p.second; // printde(findBest(ls[i]).first * 2 - ls[i], ls[i]); put(ans[i] = findBest(ls[i]).second); // put(ans[i] = findBest(ls[i]).second); } score = score0 - calc(); printde(score); for(auto& e : ans){ cout << e << '\n'; } }