// Pied!
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 155, K = 15;
int n, k, ts, rev[K][K], P[N], M[N], C[N], dp[N][3];
string S[N], T[N];
vector < int > Adj[N], Ad[N];
vector < pair < int , int > > E;
mt19937 Rnd;
inline void AddEdge(int v, int u){E.pb({u, v});}
int Find(int v) {return P[v] < 0 ? v : (P[v] = Find(P[v]));}
inline void SpanningTree()
{
for (int i = 0; i <= n; i ++)
Adj[i].clear();
shuffle(E.begin(), E.end(), Rnd);
memset(P, -1, sizeof(P));
for (auto X : E)
{
int v = Find(X.first);
int u = Find(X.second);
if (v == u)
continue;
Adj[X.first].pb(X.second);
Adj[X.second].pb(X.first);
P[v] = u;
}
}
void DFS(int v)
{
M[v] = 1;
dp[v][1] = 0;
dp[v][0] = dp[v][2] = -N;
for (int u : Adj[v])
if (!M[u])
{
DFS(u);
int dpt[3] = {-N, -N, -N};
for (int w = 0; w < 3; w ++)
dpt[w] = max(dp[v][w], dp[v][w] + dp[u][0]);
dpt[2] = max(dpt[2], dp[v][1] + dp[u][1]);
dpt[0] = max(dpt[0], dp[v][2] + dp[u][1] + 1);
dpt[0] = max(dpt[0], dp[v][1] + dp[u][2] + 1);
for (int w = 0; w < 3; w ++)
dp[v][w] = max(dp[v][w], dpt[w]);
}
}
void Build(int v, int c, int cl)
{
M[v] = cl;
if (c == 1)
{
for (int u : Adj[v])
if (!M[u]) Build(u, 0, ++ ts);
return ;
}
if (c == 2)
{
int SM = 0, opt = -1;
for (int u : Adj[v])
if (!M[u]) SM += dp[u][0];
for (int u : Adj[v])
if (!M[u] && dp[v][2] == SM - dp[u][0] + dp[u][1])
opt = u;
Build(opt, 1, cl);
for (int u : Adj[v])
if (!M[u])
Build(u, 0, ++ ts);
return ;
}
if (c == 0)
{
int SM = 0;
for (int u : Adj[v])
if (!M[u])
SM += dp[u][0];
int opt1 = -1, opt2 = -1;
for (int u1 : Adj[v])
if (!M[u1])
for (int u2 : Adj[v])
if (!M[u2] && u1 < u2)
if (dp[v][0] == SM - dp[u1][0] - dp[u2][0] + dp[u1][1] + dp[u2][1] + 1)
opt1 = u1, opt2 = u2;
if (opt1 != -1)
{
Build(opt1, 1, cl);
Build(opt2, 1, cl);
for (int u : Adj[v])
if (!M[u])
Build(u, 0, ++ ts);
return ;
}
for (int u : Adj[v])
if (!M[u] && dp[v][0] == SM - dp[u][0] + dp[u][2] + 1)
opt1 = u;
assert(opt1 != -1);
Build(opt1, 2, cl);
for (int u : Adj[v])
if (!M[u])
Build(u, 0, ++ ts);
return ;
}
}
void Recolor(int v)
{
vector < int > Mark(7, 0);
for (int u : Ad[v])
Mark[C[u]] = 1;
C[v] = 1;
while (Mark[C[v]])
C[v] ++;
for (int u : Ad[v])
if (!C[u]) Recolor(u);
}
inline bool Try()
{
SpanningTree();
memset(M, 0, sizeof(M));
iota(P, P + n + 1, 0);
shuffle(P + 1, P + n + 1, Rnd);
vector < int > rts;
memset(M, 0, sizeof(M));
for (int j = 1; j <= n; j ++)
if (!M[P[j]])
DFS(P[j]), rts.push_back(P[j]);
int SM = 0;
for (int r : rts)
SM += dp[r][0];
if (SM != n / 3)
return 0;
memset(M, 0, sizeof(M));
for (int r : rts)
Build(r, 0, ++ ts);
for (auto X : E)
{
int v = X.first;
int u = X.second;
if (M[v] != M[u])
Ad[M[v]].pb(M[u]),
Ad[M[u]].pb(M[v]);
}
for (int i = 1; i <= ts; i ++)
if (!C[i])
Recolor(i);
int cnt = 0;
for (int i = 1; i <= k + k; i ++)
{
T[i] = S[i];
for (int j = 0; j < (int)S[i].size(); j ++)
if (S[i][j] == '0')
T[i][j] = '0' + C[M[++ cnt]];
}
for (int i = 1; i <= k + k; i ++)
cout << T[i] << "\n";
exit(0);
}
inline void Solve(int TF)
{
for (int __ = 0; __ < TF; __ ++)
Try();
printf("nemoguce\n");
return ;
}
int main()
{
Rnd = mt19937(time(0));
cin >> k;
for (int i = 1; i <= k + k; i ++)
{
cin >> S[i];
for (int j = 0; j < (int)S[i].size(); j ++)
if (S[i][j] == '0')
rev[i][j] = ++ n;
for (int j = 1; j < (int)S[i].size(); j ++)
if (S[i][j] == '0' && S[i][j - 1] == '0')
AddEdge(rev[i][j], rev[i][j - 1]);
}
if (n % 3 != 0)
return !printf("nemoguce\n");
for (int i = 1; i < k; i ++)
for (int j = 0; j < (int)S[i].size(); j += 2)
if (S[i][j] == '0' && S[i + 1][j + 1] == '0')
AddEdge(rev[i][j], rev[i + 1][j + 1]);
for (int j = 0; j < (int)S[k].size(); j += 2)
if (S[k][j] == '0' && S[k + 1][j] == '0')
AddEdge(rev[k][j], rev[k + 1][j]);
for (int i = k + k; i > k + 1; i --)
for (int j = 0; j < (int)S[i].size(); j += 2)
if (S[i][j] == '0' && S[i - 1][j + 1] == '0')
AddEdge(rev[i][j], rev[i - 1][j + 1]);
int TF = 5e4;
if (k == 5)
TF = 3e4;
Solve(TF);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
86 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
201 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
229 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
384 KB |
Output is correct |
| 2 |
Correct |
38 ms |
384 KB |
Output is correct |
| 3 |
Correct |
410 ms |
392 KB |
Output is correct |
| 4 |
Correct |
6 ms |
384 KB |
Output is correct |
| 5 |
Correct |
37 ms |
384 KB |
Output is correct |
| 6 |
Correct |
441 ms |
388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
511 ms |
508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
