#pragma GCC optimize "O3" #pragma GCC target "avx" #include #include #include #include #include #include #include using namespace std; const int TIME = 1; class Timer { chrono::high_resolution_clock::time_point start, end; double limit; public: Timer() { start = chrono::high_resolution_clock::now(); } Timer(double l) { start = chrono::high_resolution_clock::now(); limit = l; } double getTime() { end = chrono::high_resolution_clock::now(); return chrono::duration(end - start).count(); } bool Over() { if (getTime() > limit) { return true; } return false; } void setLimit(double l) { limit = l; } void setStart() { start = chrono::high_resolution_clock::now(); } double getLimit() { return limit; } }; class Xor128 { unsigned static int x, y, z, w; public: Xor128() { x = 31103110, y = 123456789, z = 521288629, w = 88675123; } unsigned int rand() { unsigned int t; t = (x ^ (x << 11)); x = y; y = z; z = w; return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } }; unsigned int Xor128::x, Xor128::y, Xor128::z, Xor128::w; const double TIMELIMIT = 0.95; struct ANS { char mode; int r, c; ANS(char mode = -1, int r = 0, int c = 0):mode(mode), r(r), c(c) {} }; class Solver{ int N, K; int L[500]; int oA[60][60]; int A[60][60]; int sumA0[61][61], sumA1[61][61]; Timer tmr; Xor128 xor128; vectorans, best_ans; int best_score; public: void input() { cin >> N >> K; for (int i = 0; i < K; i++)cin >> L[i]; for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) { char a; cin >> a; a -= '0'; oA[i][j] = a; } } void init() { tmr.setStart(); for (int i = 0; i < N; i++)for (int j = 0; j < N; j++)A[i][j] = oA[i][j]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= N; j++) { sumA0[j][i] = sumA1[i][j] = 0; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { sumA0[j][i + 1] += sumA0[j][i] + A[i][j]; sumA1[i][j + 1] += sumA1[i][j] + A[i][j]; } } ans.assign(K, ANS()); best_score = 0; for (int i = 0; i < K; i++) { best_score += scoring(false, 0, 0, i); ans[i].mode = false; update(0, 0, 0, i); } best_ans = ans; tmr.setLimit(TIMELIMIT); } void SA() { double startTemp = 2, endTemp = 0.02; double diffTemp = (endTemp - startTemp) / TIMELIMIT; double current_time = tmr.getTime(); int score = best_score; bool mode2 = false; int loop = 0; int i = 0; while (current_time < TIMELIMIT) { i = (i + 1) % K; loop++; if (loop % 10000 == 0) { current_time = tmr.getTime(); if (current_time > TIMELIMIT*0.8)mode2 = true; } if (L[i] * TIMELIMIT < 15.*(TIMELIMIT - current_time))continue; int tmp2 = 0; if (ans[i].mode != -1) { int r = ans[i].r; int c = ans[i].c; int mode = ans[i].mode; if (mode) tmp2 += (sumA1[r][c + L[i]] - sumA1[r][c]); else tmp2 += (sumA0[c][r + L[i]] - sumA0[c][r]); } tmp2 *= 2; tmp2 -= L[i]; if (mode2 == false && L[i]>4) { if (tmp2 < -0.5*L[i])continue; } int change = -1e9; bool mode; int r, c; for (int t = 0; t < 2*L[i] + 2; t++) { bool tmode = xor128.rand() % 2; int tr = xor128.rand() % (N - L[i] + 1); int tc = xor128.rand() % N; if (tmode)swap(tr, tc); //if (tmode == ans[i].mode && (tmode == true && ans[i].r == tr || tmode == false && ans[i].c == tc))continue; if (t == 0) { tmode = ans[i].mode; tr = ans[i].r; tc = ans[i].c; if (tmode) { tc -= xor128.rand() % 4 + 1; if (tc < 0)continue; } else { tr -= xor128.rand() % 4 + 1; if (tr < 0)continue; } } else if (t == 1) { tmode = ans[i].mode; tr = ans[i].r; tc = ans[i].c; if (tmode) { tc += xor128.rand() % 4 + 1; if (tc >= (N - L[i] + 1))continue; } else { tr += xor128.rand() % 4 + 1; if (tr >= (N - L[i] + 1))continue; } } int tmp = scoring(tmode, tr, tc, i) + tmp2; if (t < 2) if (mode2 == false && UINT32_MAX *0.5 > xor128.rand() )continue; if (tmp >= change) { mode = tmode; r = tr; c = tc; change = tmp; } } bool accept = false; if (change >= 0)accept = true; else if (change < -2)accept = false; else { double temp = startTemp + diffTemp * tmr.getTime(); double prob = exp(change / temp); accept = prob * UINT32_MAX > xor128.rand(); } if (accept) { score += change; update(ans[i].mode, ans[i].r, ans[i].c, i); ans[i].mode = mode; ans[i].r = r; ans[i].c = c; update(mode, r, c, i); if (score > best_score) { best_score = score; best_ans = ans; } } } cerr << tmr.getTime() << endl; cerr << loop << endl; cerr << best_score << endl; } int scoring(bool mode, int r, int c, int i) { int change = 0; int* sA; if (mode)sA = sumA1[r]; else sA = sumA0[c]; if (mode) change += (sA[c + L[i]] - sA[c]); else change += (sA[r + L[i]] - sA[r]); change -= L[i]; int r1, r2; r1 = r; r2 = ans[i].r; int c1, c2; c1 = c; c2 = ans[i].c; if (mode == ans[i].mode) { if (mode == true && r1 == r2) { if (c1 > c2)swap(c1, c2); if (c1 + L[i] > c2)change += ((c1 + L[i] - c2) - 2 * (sA[c1 + L[i]] - sA[c2])); } if (mode == false && c1 == c2) { if (r1 > r2)swap(r1, r2); if (r1 + L[i] > r2)change += ((r1 + L[i] - r2) - 2 * (sA[r1 + L[i]] - sA[r2])); } } else if (ans[i].mode != -1) { if (mode) { if (c1 <= c2 && c2 <= c1 + L[i] - 1 && r2 <= r1 && r1 <= r2 + L[i] - 1) { change -= (A[r1][c2] ? 1 : -1); } } else { if (r1 <= r2 && r2 <= r1 + L[i] - 1 && c2 <= c1 && c1 <= c2 + L[i] - 1) { change -= (A[r2][c1] ? 1 : -1); } } } change *= 2; change += L[i]; return change; } void update(bool mode, int r, int c, int i) { int rev_mode = mode ^ 1; if (mode) { int p = 0; for (int j = c; j < c + L[i]; j++) { if(mode)sumA1[r][j] += p; else sumA0[j][r] += p; int p2 = (A[r][j] ? -1 : 1); for (int k = r + 1; k <= N; k++) { if(rev_mode)sumA1[k][j] += p2; else sumA0[j][k] += p2; } p += (A[r][j] ? -1 : 1); A[r][j] ^= 1; } for (int j = c + L[i]; j <= N; j++) { if (mode)sumA1[r][j] += p; else sumA0[j][r] += p; } } else { int p = 0; for (int j = r; j < r + L[i]; j++) { if (mode)sumA1[j][c] += p; else sumA0[c][j] += p; int p2 = (A[j][c] ? -1 : 1); for (int k = c + 1; k <= N; k++) { if(rev_mode)sumA1[j][k] += p2; else sumA0[k][j] += p2; } p += (A[j][c] ? -1 : 1); A[j][c] ^= 1; } for (int j = r + L[i]; j <= N; j++) { if (mode)sumA1[j][c] += p; else sumA0[c][j] += p; } } } void output() { for (int i = 0; i < K; i++) { cout << best_ans[i].r + 1 << " " << best_ans[i].c + 1 << " "; if (best_ans[i].mode)cout << best_ans[i].r + 1 << " " << best_ans[i].c + L[i] << endl; else cout << best_ans[i].r + L[i] << " " << best_ans[i].c + 1 << endl; } } int run() { init(); SA(); output(); return best_score; } }; int main() { Solver slv; slv.input(); double ave_score = 0; for (int t = 0; t < TIME; t++) { ave_score += slv.run(); } cerr << 1. * ave_score / TIME << endl; return 0; }