#line 1 "kyopro/main.cpp" #include #line 3 "kyopro_lib/base.hpp" #line 5 "kyopro_lib/base.hpp" using namespace std; using ll = long long; using ld = long double; using i2 = array; using i3 = array; using i4 = array; using f2 = array; using f3 = array; using f4 = array; template using min_pq = priority_queue, greater>; template using max_pq = priority_queue, less>; const ll INF = (1LL << 61); bool chmin(auto& a, const auto& b) { return a > b ? a = b, 1 : 0; } bool chmax(auto& a, const auto& b) { return a < b ? a = b, 1 : 0; } ll floor_div(ll a, ll b) { return a / b - (a % b != 0 && (a ^ b) < 0); } ll ceil_div(ll a, ll b) { return a / b + (a % b != 0 && (a ^ b) > 0); } ll floor_mod(ll a, ll b) { return a % b + (a % b != 0 && (a ^ b) < 0) * b; } mt19937 mt(time(0)); class xor_shift_128 { public: typedef uint32_t result_type; xor_shift_128(result_type seed = mt()) { set_seed(seed); } void set_seed(result_type seed) { a = seed = 1812433253 * (seed ^ (seed >> 30)); b = seed = 1812433253 * (seed ^ (seed >> 30)) + 1; c = seed = 1812433253 * (seed ^ (seed >> 30)) + 2; d = seed = 1812433253 * (seed ^ (seed >> 30)) + 3; } result_type gen() { result_type t = (a ^ (a << 11)); a = b; b = c; c = d; return d = (d ^ (d >> 19)) ^ (t ^ (t >> 8)); } result_type operator()() { return gen(); } ll gen_range(ll min_inclusive, ll max_exclusive) { ll diff = max_exclusive - min_inclusive; assert(diff); return min_inclusive + gen() % diff; } static constexpr result_type max() { return numeric_limits::max(); } static constexpr result_type min() { return numeric_limits::min(); } private: result_type a, b, c, d; }; xor_shift_128 xorrand; template istream& operator>>(istream& is, array& a) { for (auto& x : a) is >> x; return is; } template ostream& operator<<(ostream& os, const array& a) { for (size_t i = 0; i < N; i++) os << (i ? " " : "") << a[i]; return os; } template istream& operator>>(istream& is, vector& v) { for (auto& x : v) is >> x; return is; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < (int)v.size(); i++) os << (i ? " " : "") << v[i]; return os; } template ostream& operator<<(ostream& os, const vector>& vv) { for (int i = 0; i < (int)vv.size(); i++) os << (i ? "\n" : "") << vv[i]; return os; } #define dbg(...) cerr << #__VA_ARGS__ << " = ", debug_print(__VA_ARGS__); void debug_print() { cerr << endl; } template void debug_print(const T& x, const Args&... args) { cerr << x; if constexpr (sizeof...(args) > 0) cerr << ", "; debug_print(args...); } struct sep { const char* s; sep(const char* s) : s(s) {} }; template void print(sep sp, const Args&... args) { int i = 0; ((cout << (i++ ? sp.s : "") << args), ...); cout << "\n"; } template void print(const Args&... args) { print(sep{" "}, args...); } template void print(const vector& v) { for (int i = 0; i < (int)v.size(); i++) cout << (i ? " " : "") << v[i]; cout << "\n"; } template void print(sep sp, const vector& v) { for (int i = 0; i < (int)v.size(); i++) cout << (i ? sp.s : "") << v[i]; cout << "\n"; } #line 4 "kyopro/main.cpp" bool is_multi = false; ll mod = 998244353; void solve() { ll N; cin >> N; vector S(N); cin >> S; vector ans(N, string(N, 0)); vector> sum(N, vector(N, 0)); vector thth = { {0, 0}, {1, 0}, {-1, 0}, {0, -1}, {1, -1}, {-1, -1}, {0, 1}, {1, 1}, {-1, 1}, }; auto check = [&](ll i, ll j) -> bool { return (ans[i][j] ? (sum[i][j] <= S[i][j] - '0') : (sum[i][j] >= S[i][j] - '0')); }; ll score = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { score += check(i, j); } } auto flip = [&](ll choi, ll choj) -> ll { ll diff = 0; for (auto [di, dj] : thth) { ll i = choi + di; ll j = choj + dj; if (i < 0 || i >= N || j < 0 || j >= N) continue; diff -= check(i, j); } ll add = (ans[choi][choj] ? -1 : 1); ans[choi][choj] ^= 1; for (auto [di, dj] : thth) { ll i = choi + di; ll j = choj + dj; if (i < 0 || i >= N || j < 0 || j >= N) continue; sum[i][j] += add; } for (auto [di, dj] : thth) { ll i = choi + di; ll j = choj + dj; if (i < 0 || i >= N || j < 0 || j >= N) continue; diff += check(i, j); } return diff; }; auto calc_prob = [](ll diff, double temp) { if (diff >= 0) { return true; } return exp(diff / temp) * (1 << 16) > xorrand() % (1 << 16); }; auto modify = [&](double temp) { ll choi = xorrand() % N; ll choj = xorrand() % N; ll diff = flip(choi, choj); if (calc_prob(diff, temp)) { score += diff; } else { flip(choi, choj); } }; auto sa = [&]() { auto starttime = chrono::system_clock::now(); ll timelimit = 1900; ll bestscore = score; double starttemp = 1, endtemp = 0, nowtemp = starttemp; for (ll turn = 0; score < N * N; turn++) { if ((turn & 31) == 31) { ll timediff = duration_cast(chrono::system_clock::now() - starttime).count(); if (timediff > timelimit) { cerr << turn << endl; break; } nowtemp = endtemp - ((endtemp - starttemp) * pow(timelimit - timediff, 1)) / pow(timelimit, 1); } modify(nowtemp); } }; sa(); for (auto& x : ans) for (auto& y : x) y = (y ? 'o' : '.'); print(sep("\n"), ans); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); ll tests = 1; if (is_multi) { cin >> tests; } while (tests--) { solve(); } return 0; }