/*input
2
0000.
0000000
..00.0.
.0000
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
struct grupe
{
int x, y, z;
bool reikia = false;
};
vector<grupe>xx;
vector<char>col = {'.'};
int kiek = 0;
vector<int>adj[1000];
bool ieskom(int i)
{
if (kiek == 0)
return true;
if (i == (int)xx.size())
{
return false;
}
if (col[xx[i].x] != '0' || col[xx[i].y] != '0' || col[xx[i].z] != '0')
{
return ieskom(i + 1);
}
col[xx[i].x] = '1';
col[xx[i].y] = '1';
col[xx[i].z] = '1';
xx[i].reikia = true;
kiek -= 3;
{
set<int>aplink;
for (int i : {xx[i].x, xx[i].y, xx[i].z})
for (int j : adj[i])
aplink.insert(j);
bool ok = true;
for (int x : aplink)
{
if (col[x] == '0')
{
int kiek = 0;
int yy = x;
for (int y : adj[x])
{
if (col[y] == '0')
{
yy = y;
kiek++;
}
}
if (kiek == 0)
ok = false;
else if (kiek == 1)
{
for (int y : adj[yy])
{
if (col[y] == '0')
{
kiek++;
}
}
if (kiek == 2)
ok = false;
}
}
}
if (ok && ieskom(i + 1))
return true;
}
xx[i].reikia = false;
kiek += 3;
col[xx[i].x] = '0';
col[xx[i].y] = '0';
col[xx[i].z] = '0';
return ieskom(i + 1);
}
int main()
{
ios_base::sync_with_stdio(false);
int n;
cin >> n;
string s[2 * n];
for (int i = 0; i < 2 * n; i++)
cin >> s[i];
vector<int>id[2 * n];
int timer = 1;
for (int i = 0; i < 2 * n; i++)
for (char c : s[i])
{
id[i].push_back(timer++);
col.push_back(c);
if (c == '0')
kiek++;
}
for (int i = 0; i < 2 * n; i++)
{
for (int t = 0; t + 1 < (int)id[i].size(); t++)
{
int x = id[i][t];
int y = id[i][t + 1];
adj[x].push_back(y);
adj[y].push_back(x);
}
}
for (int i = 0; i <= n - 2; i++)
{
for (int t = 0; t < (int)id[i].size(); t += 2)
{
int x = id[i][t];
int y = id[i + 1][t + 1];
adj[x].push_back(y);
adj[y].push_back(x);
}
}
for (int t = 0; t < (int)id[n - 1].size(); t += 2)
{
int x = id[n - 1][t];
int y = id[n][t];
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = n + 1; i < 2 * n; i++)
{
for (int t = 0; t < (int)id[i].size(); t += 2)
{
int x = id[i][t];
int y = id[i - 1][t + 1];
adj[x].push_back(y);
adj[y].push_back(x);
}
}
for (int i = 1; i < timer; i++)
{
for (int j : adj[i])
{
for (int k : adj[i])
{
if (j < k)
{
grupe a;
a.x = i;
a.y = j;
a.z = k;
if (col[a.x] == '0' && col[a.y] == '0' && col[a.z] == '0')
xx.push_back(a);
}
}
}
}
if (ieskom(0))
{
for (grupe a : xx)
{
if (a.reikia == false)
continue;
set<int>aplink;
for (int i : {a.x, a.y, a.z})
for (int j : adj[i])
aplink.insert(j);
for (int i : {a.x, a.y, a.z})
aplink.erase(i);
set<char>cols;
for (int i : aplink)
cols.insert(col[i]);
for (char x = '1'; x <= '6'; x++)
if (cols.count(x) == 0)
{
col[a.x] = x;
col[a.y] = x;
col[a.z] = x;
}
}
for (int i = 0; i < 2 * n; i++)
{
for (int t = 0; t < (int)id[i].size(); t++)
{
cout << col[id[i][t]];
}
cout << endl;
}
}
else
cout << "nemoguce\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
65 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Execution timed out |
1065 ms |
384 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1068 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
512 KB |
Output is correct |
| 2 |
Correct |
13 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
440 KB |
Output is correct |
| 4 |
Execution timed out |
1074 ms |
384 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
