## Editorial for Slikar

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
maxn=512;
maxc=1000000000;
dx:array[1..4] of longint=(-1,-1,0,0);
dy:array[1..4] of longint=(-1,0,-1,0);
var n,m:longint;
a,re:array[1..maxn,1..maxn] of byte;
min,b,tr:array[0..9,1..maxn,1..maxn] of longint;
p:array[0..9] of longint;
d:array[1..4] of byte;
dt:array[1..9,1..maxn div 2,1..maxn div 2,1..4] of byte;

procedure rf;
var i,j:longint; c:char;
begin
assign(input,fi);
reset(input);
for i:=1 to n do
begin
for j:=1 to n do
begin
if c='0' then
begin
a[i,j]:=0;
b[0,i,j]:=0;
end
else
begin
a[i,j]:=1;
b[0,i,j]:=1;
end;
end;
end;
re:=a;
p[0]:=1;
for i:=1 to 9 do p[i]:=p[i-1] shl 1;
close(input);
end;

procedure fill2(deg,x,y,val:longint);
var i,j:longint;
begin
for i:=p[deg]*(x-1)+1 to p[deg]*x do
for j:=p[deg]*(y-1)+1 to p[deg]*y do
re[i,j]:=val;
end;

procedure fill(deg,x,y:longint);
var i,j,p,q:longint;
begin
p:=tr[deg,x,y] div 10; q:=tr[deg,x,y] mod 10;
fill2(deg-1,2*x+dx[p],2*y+dy[p],0);
fill2(deg-1,2*x+dx[q],2*y+dy[q],1);
if deg=1 then exit;
dt[deg,x,y,p]:=1; dt[deg,x,y,q]:=1;
for i:=1 to 4 do
if dt[deg,x,y,i]=0 then fill(deg-1,2*x+dx[i],2*y+dy[i]);
end;

procedure pr;
var i,j,k,t,r,q,s,u:longint; kt:boolean;
begin
for i:=1 to 9 do
begin
t:=n div p[i];
if t=0 then break;
for j:=1 to t do
for k:=1 to t do
begin
min[i,j,k]:=maxc;
r:=2*j; q:=2*k;
b[i,j,k]:=b[i-1,r-1,q-1]+b[i-1,r-1,q]+b[i-1,r,q-1]+b[i-1,r,q];
end;
end;
m:=i-1;
if n=512 then m:=9;
for i:=1 to m do
begin
t:=n div p[i];
for j:=1 to t do
for k:=1 to t do
begin
kt:=false;
for r:=1 to 4 do
if kt then break
else
for q:=1 to 4 do
if r<>q then
begin
fillchar(d,sizeof(d),0);
d[r]:=1; d[q]:=1;
s:=b[i-1,2*j+dx[r],2*k+dy[r]]+p[i-1]*p[i-1]-b[i-1,2*j+dx[q],2*k+dy[q]];
for u:=1 to 4 do
if d[u]=0 then
s:=s+min[i-1,2*j+dx[u],2*k+dy[u]];
if s<min[i,j,k] then
begin
min[i,j,k]:=s;
kt:=s=0;
tr[i,j,k]:=r*10+q;
if kt then break;
end;
end;
end;
end;
fill(m,1,1);
end;

procedure wf;
var i,j:longint;
begin
assign(output,fo);
rewrite(output);
writeln(min[m,1,1]);
for i:=1 to n do
begin
for j:=1 to n do
write(re[i,j]);
writeln;
end;
close(output);
end;

begin
rf;
pr;
wf;
end.

{$H+} program slikar; uses math; const maxn=513; maxP = 10; oo=trunc(1e9); fi=''; b = 1;//black; w = 0;//white; r = 2;//recursive; var f:array[1..maxn,1..maxn,0..maxP,0..2] of longint; //F[i,j,k,t] = Chenh lech min cua hinh vuong goc duoi phai la i,j, canh = 2^k, to theo cach t; check:array[1..maxn,1..maxn,0..maxP,0..2] of boolean; trace:array[1..maxn,1..maxn,0..maxP] of longint; res:array[1..maxn,1..maxn] of longint; a:array[1..maxn] of string; pow:array[0..10] of longint; per:array[0..30,0..4] of longint; n,pn,d:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi);reset(inp); readln(inp,n); for i:=1 to n do readln(inp,a[i]); close(inp); pow[0]:=1; for i:=1 to 10 do pow[i]:=2*pow[i-1]; for i:=0 to 10 do if pow[i] = n then pn:=i; end; procedure GenPer; var i,k,j,t:longint; begin for i:=1 to 3 do for j:=i+1 to 4 do for t:=0 to 1 do begin inc(d); per[d,i]:=2;per[d,j]:=2; for k:=1 to 4 do if (k<>i) and (k<>j) then begin per[d,k]:=t; break; end; for k:=4 downto 1 do if (k<>i) and (k<>j) then begin per[d,k]:=1-t; break; end; end; end; function dp(i,j,k,t:longint):longint; var i1,i2,i3,j1,j2,j3,x,temp:longint; begin if check[i,j,k,t] then exit(f[i,j,k,t]); check[i,j,k,t]:=true; if k=0 then begin if (t=2) or (a[i][j] = chr(t+48)) then f[i,j,k,t]:=0 else f[i,j,k,t]:=1; exit(f[i,j,k,t]); end; i1:=(i+i-pow[k]) shr 1; j1:=(j+j-pow[k]) shr 1; i2:=i1;j2:=j; i3:=i; j3:=j1; if (t<2) then f[i,j,k,t]:=dp(i1,j1,k-1,t)+dp(i2,j2,k-1,t)+dp(i3,j3,k-1,t)+dp(i,j,k-1,t) else begin f[i,j,k,t]:=oo; for x:=1 to d do begin temp:= dp(i1,j1,k-1,per[x,1])+dp(i2,j2,k-1,per[x,2])+ dp(i3,j3,k-1,per[x,3])+dp(i,j,k-1,per[x,4]); if f[i,j,k,t]>temp then begin f[i,j,k,t]:=temp; trace[i,j,k]:=x; end; end; end; exit(f[i,j,k,t]); end; procedure print(i,j,k,t:longint); var p,q,i1,i2,i3,j1,j2,j3:longint; begin if (t<2) then begin for p:=i-pow[k]+1 to i do for q:=j-pow[k]+1 to j do res[p,q]:=t; exit; end; if k=0 then begin res[i,j]:=ord(a[i][j])-48; exit; end; i1:=(i+i-pow[k]) shr 1; j1:=(j+j-pow[k]) shr 1; i2:=i1;j2:=j; i3:=i; j3:=j1; print(i1,j1,k-1,per[trace[i,j,k],1]); print(i2,j2,k-1,per[trace[i,j,k],2]); print(i3,j3,k-1,per[trace[i,j,k],3]); print(i,j,k-1,per[trace[i,j,k],4]); end; procedure process; var i,j:longint; begin writeln(dp(n,n,pn,r)); print(n,n,pn,r); for i:=1 to n do begin for j:=1 to n do write(res[i,j]); writeln; end; end; begin input; GenPer; process; end. #### Code mẫu của RR {$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=512;
snode=400000;
var
f1,f2:text;
vt0,vt1,vtx,vty,vt,n:longint;
//  timeold:longint;
kq,a:array[1..MAXN,1..MAXN] of longint;
color,diff1,diff0,diff,s0,s1:array[1..snode] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i,j:longint;
ch:char;
begin
for i:=1 to n do
begin
for j:=1 to n do
begin
if ch='0' then a[i,j]:=0 else a[i,j]:=1;
end;
end;
end;
procedure build(i,u1,u2,v1,v2:longint);
var
mu,mv:longint;
begin
if (u1=u2) then
begin
if a[u1,v1]=0 then
begin
s0[i]:=1; s1[i]:=0;
diff0[i]:=0; diff1[i]:=1;
diff[i]:=0;
end
else //a[u1,v1]=1
begin
s0[i]:=0; s1[i]:=1;
diff0[i]:=1; diff1[i]:=0;
diff[i]:=0;
end;
exit;
end;
mu:=(u1+u2)>>1; mv:=(v1+v2)>>1;
build(i<<2-2,u1,  mu,v1,mv); build(i<<2-1,u1,  mu,mv+1,v2);
build(i<<2  ,mu+1,u2,v1,mv); build(i<<2+1,mu+1,u2,mv+1,v2);
s0[i]:=s0[i<<2-2]+s0[i<<2-1]+s0[i<<2]+s0[i<<2+1];
s1[i]:=s1[i<<2-2]+s1[i<<2-1]+s1[i<<2]+s1[i<<2+1];
diff0[i]:=s1[i]; diff1[i]:=s0[i];
diff[i]:=maxlongint;
for vt0:=i<<2-2 to i<<2+1 do
for vt1:=i<<2-2 to i<<2+1 do
if vt0<>vt1 then
begin
vtx:=0; vty:=0;
for vt:=i<<2-2 to i<<2+1 do
if (vt<>vt0) and (vt<>vt1) then
if vtx=0 then vtx:=vt else vty:=vt;
diff[i]:=min(diff[i],diff0[vt0]+diff1[vt1]+diff[vtx]+diff[vty]);
end;
end;
var
i,j:longint;
procedure cal(i,u1,u2,v1,v2,k:longint);
var
mu,mv:longint;
begin
if k=0 then exit;
if k=1 then
begin
for i:=u1 to u2 do
for j:=v1 to v2 do
kq[i,j]:=k;
exit;
end;
if u1=u2 then
begin
kq[u1,v1]:=a[u1,v1];
exit;
end;
mu:=(u1+u2)>>1; mv:=(v1+v2)>>1;
for vt0:=i<<2-2 to i<<2+1 do
for vt1:=i<<2-2 to i<<2+1 do
if vt0<>vt1 then
begin
vtx:=0; vty:=0;
for vt:=i<<2-2 to i<<2+1 do
if (vt<>vt0) and (vt<>vt1) then
if vtx=0 then vtx:=vt else vty:=vt;
if diff[i]=diff0[vt0]+diff1[vt1]+diff[vtx]+diff[vty] then
begin
color[vt0]:=0; color[vt1]:=1; color[vtx]:=2; color[vty]:=2;
cal(i<<2-2,u1,  mu,v1,  mv,color[i<<2-2]);
cal(i<<2-1,u1,  mu,mv+1,v2,color[i<<2-1]);
cal(i<<2  ,mu+1,u2,v1,  mv,color[i<<2  ]);
cal(i<<2+1,mu+1,u2,mv+1,v2,color[i<<2+1]);
exit;
end;
end;
end;
procedure ans;
begin
writeln(f2,diff[1]);
for i:=1 to n do
begin
for j:=1 to n do write(f2,kq[i,j]);
writeln(f2);
end;
end;
begin
//  timeold:=getTickCount;
openF;
inp;
build(1,1,n,1,n);
cal(1,1,n,1,n,2);
ans;
closeF;
//  writeln(getTickCount-timeold);
end.

#### Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
//typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {-1, +0, +1, +0};
const int dc[] = {+0, +1, +0, -1};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ld eps = ld(1e-9);
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 515

int n, m;
string s[maxn], res[maxn];
int a[maxn][maxn][11], f[maxn][maxn][11], d[maxn][maxn][11][2];

int cal2(int x){
if(x == 1) return 0;
return 1 + cal2(x >> 1);
}

int B(int x){
return 1 << x;
}

void Boi(int r, int c, int id, int mau){
For(i, r, r + B(id) - 1) For(j, c, c + B(id) - 1)
res[i][j] = mau + '0';
}

void paint(int r, int c, int id){
if(id == 0){
res[r][c] = s[r][c];
return;
}
int i = d[r][c][id][0];
int j = d[r][c][id][1];
int t1 = -1, t2;
Rep(k, 4) if(k != i && k!= j){
if(t1 == -1) t1 = k;
else t2 = k;
}
Boi(r + (i >> 1) * B(id - 1), c + (i & 1) * B(id - 1), id - 1, 0);
Boi(r + (j >> 1) * B(id - 1), c + (j & 1) * B(id - 1), id - 1, 1);
paint(r + (t1 >> 1) * B(id - 1), c + (t1 & 1) * B(id - 1), id - 1);
paint(r + (t2 >> 1) * B(id - 1), c + (t2 & 1) * B(id - 1), id - 1);
}

void go(int r, int c, int id){
if(id == 0) {f[r][c][id] = 0; return;}
go(r, c, id - 1);
go(r, c + B(id - 1), id - 1);
go(r + B(id - 1), c, id - 1);
go(r + B(id - 1), c + B(id - 1), id - 1);
int &res = f[r][c][id];
res = inf;
Rep(i, 4) Rep(j, 4) if(i != j){
int t, t1 = -1, t2;
Rep(k, 4) if(k != i && k!= j){
if(t1 == -1) t1 = k;
else t2 = k;
}
t = a[r + (i >> 1) * B(id - 1)][c + (i & 1) * B(id - 1)][id - 1]
+ B(id + id - 2) - a[r + (j >> 1) * B(id - 1)][c + (j & 1) * B(id - 1)][id - 1]
+ f[r + (t1 >> 1) * B(id - 1)][c + (t1 & 1) * B(id - 1)][id - 1]
+ f[r + (t2 >> 1) * B(id - 1)][c + (t2 & 1) * B(id - 1)][id - 1];
if(t < res){
res = t;
d[r][c][id][0] = i;
d[r][c][id][1] = j;
}
}
// if(r == 0 && c == 0 && id == m) cout << res << endl;
}

int main(){
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
cin >> n;
Rep(i, n) cin >> s[i];
Rep(i, n) Rep(j, n) a[i][j][0] = s[i][j] - '0';
m = cal2(n);
Rep(i, n) res[i].resize(n);
For(i, 1, m){
For(r, 0, n - (1 << i))
For(c, 0, n - (1 << i)){
a[r][c][i] = a[r][c][i - 1] + a[r + B(i - 1)][c][i - 1]
+a[r][c + B(i - 1)][i - 1] + a[r + B(i - 1)][c + B(i - 1)][i - 1];
}
}
go(0, 0, m);
paint(0, 0, m);
printf("%d\n", f[0][0][m]);
Rep(i, n) cout << res[i] << endl;
}

#### Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int mx[4] = {0,0,1,1};
int my[4] = {0,1,0,1};
int n;
int a[520][520],b[520][520],fin[520][520];
int f[520][520][11],p0[520][520][11],p1[520][520][11];

int get(int x1,int y1,int x2,int y2)
{
return b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1];
};

int rec(int x,int y,int k)
{
if (f[x][y][k] != -1) return f[x][y][k];
if (!k)
{
f[x][y][k] = 0;  return 0;
};

int best = 1000000000,len = 1 << (k - 1);
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++) if (i != j)
{
int tmp = get(x + len * mx[i],y + len * my[i],x - 1 + len * mx[i] + len,y - 1 + len * my[i] + len);  //color with 0
tmp += len * len - get(x + len * mx[j],y + len * my[j],x - 1 + len * mx[j] + len,y - 1 + len * my[j] + len);  //color with 1
for (int t = 0; t < 4; t++) if (t != i && t != j)
tmp += rec(x + len * mx[t],y + len * my[t],k - 1);
if (best > tmp)
{
best = tmp;  p0[x][y][k] = i;  p1[x][y][k] = j;
};
};

f[x][y][k] = best;  return best;
};

void track(int x,int y,int k)
{
if (!k)
{
fin[x][y] = a[x][y];  return;
};
int pos = p1[x][y][k],len = 1 << (k - 1);
for (int i = x + len * mx[pos]; i < x + len * mx[pos] + len; i++)
for (int j = y + len * my[pos]; j < y + len * my[pos] + len; j++) fin[i][j] = 1;
for (int t = 0; t < 4; t++) if (t != p0[x][y][k] && t != p1[x][y][k]) track(x + len * mx[t],y + len * my[t],k - 1);
};

int main()
{
//    freopen("slikar.in","r",stdin);
//    freopen("slikar.ou","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
char ch;
while (1)
{
scanf("%c", &ch);
if (ch == '0' || ch == '1') break;
};
a[i][j] = ch - '0';
};

/*    for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++) cout << a[i][j];
cout << endl;
};*/

memset(b,0,sizeof(b));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) b[i][j] = a[i][j];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= n; j++) b[i][j] += b[i - 1][j];
for (int i = 1; i <= n; i++)
for (int j = 2; j <= n; j++) b[i][j] += b[i][j - 1];

memset(f,-1,sizeof(f));
int tmp = n,k = 0;
while (tmp > 1)
{
tmp /= 2;  k++;
};

int ret = rec(1,1,k);
memset(fin,0,sizeof(fin));
track(1,1,k);
printf("%d\n", ret);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++) printf("%d", fin[i][j]);
printf("\n");
};
};

#### Code mẫu của khuc_tuan

// {$APPTYPE CONSOLE} {$mode delphi}

uses math, sysutils;

const
dx : array[1..4] of integer = (0,0,1,1);
dy : array[1..4] of integer = (0,1,0,1);

type
Data = class
b, w, r : integer;
end;

var
n, i, j : integer;
a, b : array[1..555,1..555] of char;

procedure fill(sx, sy, len : integer; c : char);
var
i, j : integer;
begin
for i:= sx to sx + len - 1 do
for j:= sy to sy + len - 1 do
b[i,j] := c;
end;

function color(sx, sy, len : integer) : Data;
var
res : Data;
kq : array[1..4] of Data;
cur, best, btr, bde, tr, de, i, j, z : integer;
begin
res := Data.Create;

for i:=sx to sx + len - 1 do
for j:=sy to sy + len - 1 do
if a[i,j]='0' then inc(res.b)
else inc(res.w);

if len = 1 then
begin
b[sx,sy] := a[sx,sy];
// if b[sx,sy] <> a[sx,sy] then inc(res.r);
color := res;
exit;
end;

z := len div 2;

for i:=1 to 4 do
kq[i] := color( sx + dx[i] * z, sy + dy[i] * z, z);

best := 1000000000;

for tr := 1 to 4 do
for de := 1 to 4 do if de <> tr then
begin
cur := kq[tr].w + kq[de].b;
for i := 1 to 4 do if (i<>de) and (i<>tr) then cur := cur + kq[i].r;
if cur < best then
begin
best := cur;
btr := tr;
bde := de;
end;
end;

fill( sx + dx[btr] * z, sy + dy[btr] * z, z, '0');
fill( sx + dx[bde] * z, sy + dy[bde] * z, z, '1');

res.r := best;
color := res;
end;

begin
for i:=1 to n do
begin
for j:=1 to n do read(a[i,j]);
end;

writeln(color(1, 1, n).r);
for i:=1 to n do
begin
for j:=1 to n do
write(b[i,j]);
writeln;
end;
end.