QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#30011 | #2898. Diagonals | George_Plover | WA | 5ms | 3704kb | C++ | 6.0kb | 2022-04-24 02:38:56 | 2022-04-28 12:18:40 |
Judging History
answer
#include <bits/stdc++.h>
#define G 12
#define B 64
using namespace std;
using ull = unsigned long long;
ull b[B], h[B >> 2];
map<ull, ull> m[2];
char g[G][G];
int n;
inline int get_b(ull x, int p) { return x >> p & 1; }
inline int get_h(ull x, int p) { return (x >> (p << 2)) & 0xf; }
inline ull set_b(ull x, int p, int v) { return x ^ (x & b[p]) ^ ((v & 1) << p); }
inline ull set_h(ull x, int p, int v) { return x ^ (x & h[p]) ^ ((v & 0xf) << (p << 2)); }
void debug_s(ull s, bool e = true)
{
for (int i = 0; i <= n; i++)
cerr.put(get_b(s, i) ? '/' : '\\');
if (e)
cerr.put('\n');
}
void debug_t(ull t, bool e = true)
{
for (int i = 0; i <= n; i++)
cerr << hex << get_h(t, i);
if (e)
cerr.put('\n');
}
void debug(ull z, bool e = true)
{
cerr << "S ";
debug_s(z & (b[n + 1] - 1), false);
cerr << " T ";
debug_t(z >> (n + 1), e);
}
inline bool same_con(ull t, int x, int y) { return get_h(t, x) == get_h(t, y); }
int max_con(ull t)
{
int x = 0;
for (int i = 0; i <= n; i++)
x = max(x, get_h(t, i));
return x;
}
bool check(int i, int j, ull s, ull t, bool k)
{
if (!j)
{
if (g[i][j] != '+' && get_b(s, 1) + !k != g[i][j] - '0')
return false;
}
else
{
if (g[i][j] != '+' && !get_b(s, 0) + get_b(s, 1) + get_b(s, n) + !k != g[i][j] - '0')
return false;
}
if (j == n - 1 && g[i][n] != '+' && !get_b(s, 1) + k != g[i][n] - '0')
return false;
if (i == n - 1)
{
if (!j)
{
if (g[n][j] != '+' && k != g[n][j] - '0')
return false;
}
else
{
if (g[n][j] != '+' && !get_b(s, n) + k != g[n][j] - '0')
return false;
}
if (j == n - 1 && g[n][n] != '+' && k == g[n][n] - '0')
return false;
}
if (k && j && !get_b(s, n))
{
if (!get_b(s, 1) && same_con(t, 1, n))
return false;
if (j < n - 1 && get_b(s, 2) && same_con(t, 2, n))
return false;
}
return true;
}
ull merge_con(ull t, int x, int y)
{
x = get_h(t, x);
y = get_h(t, y);
if (x != y)
for (int i = 0; i <= n; i++)
if (get_h(t, i) == y)
t = set_h(t, i, x);
return t;
}
ull relabel_con(ull t)
{
int o[9] = {0};
for (int i = 0, k = 0; i <= n; i++)
{
int j = get_h(t, i);
if (!o[j])
o[j] = ++k;
}
for (int i = 0; i <= n; i++)
t = set_h(t, i, o[get_h(t, i)] - 1);
return t;
}
ull next_state(int j, ull s, ull t, bool k)
{
ull u = set_b(s >> 1, n, k), v = set_h(t >> 4, n, !k && j && !get_b(s, 0) ? get_h(t, 0) : max_con(t) + 1);
// cerr << "0 ";
// debug_t(v);
if (!k)
{
if (get_b(u, 0))
{
v = merge_con(v, 0, n);
// cerr << "1 ";
// debug_t(v);
}
if (j && get_b(u, n - 1))
{
v = merge_con(v, n - 1, n);
// cerr << "2 ";
// debug_t(v);
}
}
else
{
if (!get_b(u, 0))
{
v = merge_con(v, 0, n);
// cerr << "3 ";
// debug_t(v);
}
if (j && !get_b(u, n - 1))
{
v = merge_con(v, n - 1, n);
// cerr << "4 ";
// debug_t(v);
}
if (j < n - 1 && get_b(u, 1))
{
v = merge_con(v, 1, n);
// cerr << "5 ";
// debug_t(v);
}
}
v = relabel_con(v);
// cerr << "6 ";
// debug_t(v);
return v << (n + 1) | u;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < B; i++)
b[i] = 1ull << i;
for (int i = 0; i < B >> 2; i++)
h[i] = 0xfull << (i << 2);
cin >> n;
for (int i = 0; i <= n; i++)
cin >> g[i];
if (n == 1)
{
cout << (g[0][0] != '0' && g[1][1] != '0' && (g[0][0] == '1' || g[1][1] == '1' || g[0][1] == '0' || g[1][0] == '0') ? "\\\n" : "/\n");
return 0;
}
for (ull s = 0; s < b[n]; s++)
{
if (g[0][0] != '+' && get_b(s, 0) == g[0][0] - '0')
continue;
if (g[0][n] != '+' && get_b(s, n - 1) != g[0][n] - '0')
continue;
bool z = true;
for (int i = 1; z && i < n; i++)
z &= g[0][i] == '+' || get_b(s, i - 1) + !get_b(s, i) == g[0][i] - '0';
if (z)
{
ull t = 0;
for (int i = 0, j = 0; i < n; i++)
{
j += !i || get_b(s, i - 1) == get_b(s, i);
t = set_h(t, i + 1, j);
}
m[0][(t << n | s) << 1] = s;
}
}
bool z = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n; j++, z ^= 1)
{
m[z ^ 1].clear();
for (auto &v : m[z])
{
ull s = v.first & (b[n + 1] - 1), t = v.first >> (n + 1);
// cerr << "I " << i << " J " << j << ' ';
// debug(v.first);
for (int k = 0; k < 2; k++)
{
if (check(i, j, s, t, k))
{
ull zzz = next_state(j, s, t, k);
// cerr << " K " << k << ' ';
// debug(zzz);
m[z ^ 1][zzz] = k ? (v.second | b[i * n + j]) : v.second;
}
}
}
// cerr.put('\n');
}
}
if (!m[z].empty())
{
ull r = m[z].cbegin()->second;
for (int i = 0; i < n; i++, cout.put('\n'))
for (int j = 0; j < n; j++, r >>= 1)
cout.put((r & 1) ? '/' : '\\');
}
else
for (;;)
cout << "FUCK YOU!\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 3704kb
input:
8 +11+111++ 1++++1++0 1++2++3++ +1+2+1+3+ +213+++++ 12+232+++ 222+++22+ +++3+3+++ +211+121+
output:
///\\\\/ //\/\//\ /\\///\/ //\/\/\\ //////// ////\\\\ \\\/\/// \///\\//
result:
wrong answer 1st lines differ - expected: '////////', found: '///\\\\/'