QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#30012 | #2898. Diagonals | George_Plover | AC ✓ | 52ms | 4884kb | C++ | 6.2kb | 2022-04-24 02:51:18 | 2022-04-28 12:18:43 |
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 & 1ull) << p); }
inline ull set_h(ull x, int p, int v) { return x ^ (x & h[p]) ^ ((v & 0xfull) << (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));
// cerr << "CON ";
// debug_t(t, false);
// cerr << " MAX " << x << '\n';
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++)
{
// cerr << "CHECK K " << k << '\n';
if (check(i, j, s, t, k))
{
// cerr << "CHECK PASSED!\n";
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: 100
Accepted
time: 3ms
memory: 3612kb
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:
ok 8 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 3624kb
input:
8 ++++++11+ +13+13++1 ++21+21++ +11+2222+ +2++3++21 +11+1+2+1 +++322+1+ 11+1+1+11 +1++1++++
output:
/\/\\/// \\\\//\/ /\\////\ \\/////\ //\/\//\ \//////\ /\/\\\// //\\\/\/
result:
ok 8 lines
Test #3:
score: 0
Accepted
time: 3ms
memory: 3768kb
input:
8 ++1+++2++ 12++23++2 0222322++ +3+11+3+1 ++++++++1 +213+2++0 +1+3++22+ 2++22+4++ +1+++1+++
output:
\\\\\/\\ \\\\\\\/ ////\\\/ /\\///\/ /\\//\\/ /\///\/\ ///\/\/\ \\/\//\\
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 3ms
memory: 3472kb
input:
5 +1+2++ 1++11+ +3+2++ 02+++1 ++3+1+ +1+++1
output:
\\/\\ \/\\/ \\\\\ ////\ //\\\
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
5 +++21+ 11+2++ 1++2++ ++32+1 +3++3+ ++0+++
output:
\\/\\ \//\/ \\/\/ \//\/ //\\\
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 ++1+++ 12+++1 +2121+ +2+22+ +323++ ++++1+
output:
////\ ////\ \\/// \\/// /\/\\
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 11ms
memory: 3872kb
input:
8 +++++++++ ++4+++22+ +3+++3+3+ ++++2+3++ ++1++++21 ++21++3++ +2+++++21 +4+1+2+11 ++++2+1+0
output:
\\//\\\/ \/\\\\\/ //\\/\// //\\//// \//\\\// \/////// \//\/\// /\\\/\\/
result:
ok 8 lines
Test #8:
score: 0
Accepted
time: 3ms
memory: 3680kb
input:
1 01 10
output:
/
result:
ok single line: '/'
Test #9:
score: 0
Accepted
time: 3ms
memory: 3576kb
input:
1 0+ ++
output:
/
result:
ok single line: '/'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
1 10 01
output:
\
result:
ok single line: '\'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
1 1+ ++
output:
\
result:
ok single line: '\'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
1 +0 ++
output:
\
result:
ok single line: '\'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
1 +1 ++
output:
/
result:
ok single line: '/'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
1 ++ 0+
output:
\
result:
ok single line: '\'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
1 ++ 1+
output:
/
result:
ok single line: '/'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
1 ++ +0
output:
/
result:
ok single line: '/'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
1 ++ +1
output:
\
result:
ok single line: '\'
Test #18:
score: 0
Accepted
time: 4ms
memory: 3656kb
input:
8 +++++++++ +1+2+32+1 ++32++4++ +2+4++++1 +3+++++11 ++21++3+0 +2++23+++ ++1++++1+ +110+0+10
output:
/\\/\\// \\\//\// \/\///\/ \//\\/// ///\\\\/ \\\\\/\\ //\////\ ///\/\//
result:
ok 8 lines
Test #19:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
8 +++++++++ +3+2+2+20 +2+4+3+++ ++1++2++1 +3++2+++1 +++21+2+2 ++2++24++ +2+3++++1 +2+112+2+
output:
\/\/\/// \\\/\/\\ ///\\\\\ \\//\\/\ /\//\\/\ //\\\\// \/\///\/ \/\\\/\/
result:
ok 8 lines
Test #20:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
7 ++++++++ +23131+1 +11+1+2+ ++2++1+1 +3++3+++ ++22222+ +3+3222+ ++2+1+2+
output:
/////\/ //\/\\/ \////\/ \//\/// \\\\\\/ \\\\\\/ /\/\\\/
result:
ok 7 lines
Test #21:
score: 0
Accepted
time: 3ms
memory: 3616kb
input:
7 ++++++++ +21221+0 +++1+3++ +3+2++21 +233++2+ +++++2+1 +21+2++1 +++12+2+
output:
/////\/ \\////\ \/\//\\ \\\//\\ //\\/// //\\/// \\\\/\/
result:
ok 7 lines
Test #22:
score: 0
Accepted
time: 6ms
memory: 3644kb
input:
8 +++++++++ +2+233+21 +24++2+21 ++++++1+1 +3++21+22 +23+++3++ +++3+++11 +21++21+0 +1110++1+
output:
\\\\\/\\ \\//\\\\ //\///\\ \////\\\ \\\\\\// //\///// //\\//\/ ////\\\\
result:
ok 8 lines
Test #23:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
8 +++++++++ +11+1+4+0 ++2++3+++ +131+++1+ ++1+3+320 +2+2+11++ +23+1+2++ +31++1++1 +0+112+0+
output:
//\/\\// \//\\/\\ ///\///\ \/\\//// //////\\ ////\//\ //\////\ /\\\\//\
result:
ok 8 lines
Test #24:
score: 0
Accepted
time: 3ms
memory: 3696kb
input:
7 ++++++++ +24++1+1 ++++2+3+ ++23+231 +3++2+++ +33+121+ ++++++2+ ++0+11+1
output:
\\///\/ //\/\\/ \\\/\\\ \/////\ \\////\ /\\\/// //\\\\\
result:
ok 7 lines
Test #25:
score: 0
Accepted
time: 5ms
memory: 3708kb
input:
7 ++++++++ +232+2+1 +++2++3+ +322+2++ ++24+1+2 ++++++2+ +2++2+4+ +0+10+++
output:
\\\//\/ //\//\/ \\\//\\ /\\//\\ ///\\\/ /\//\\/ /\//\/\
result:
ok 7 lines
Test #26:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
8 +++++++++ ++3+3+3++ +3+3+3+3+ ++3+++3++ +3+++++2+ ++3+++32+ +3+3+3+31 ++3+2+3++ +++++++++
output:
\\\\\\// \/\/\/// \\\\\\/\ \/\\/\\\ \\\/\\\\ \/\\\/\\ ///\///\ //\\//\\
result:
ok 8 lines
Test #27:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
3 ++++ +1+1 +31+ +0+0
output:
/\/ /// /\/
result:
ok 3 lines
Test #28:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
4 +++++ +3++2 ++3++ +3+3+ ++2+0
output:
\//\ \\// \\\/ /\//
result:
ok 4 lines
Test #29:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
7 ++++++++ +3+3+3++ ++3++23+ +3+++321 ++3+++3+ +3+++3++ ++3+3+3+ +++1++++
output:
\\\/\// /\//\\/ ///\\\\ /\///\\ ///\//\ /\/\/\\ //////\
result:
ok 7 lines
Test #30:
score: 0
Accepted
time: 7ms
memory: 3808kb
input:
8 +++++++++ +3+24+++2 ++4+++2++ +++++21+1 +3+3++2++ ++3+2++2+ +++3+++3+ ++++3+3+2 +2+2+2+2+
output:
\\\\//\\ /\//\/\/ //\///\/ \\\///// /\\\\\\/ //\//\\/ \/\\\\\\ \/\/\/\/
result:
ok 8 lines
Test #31:
score: 0
Accepted
time: 11ms
memory: 3772kb
input:
8 +++++++++ +22+2+2+1 +32+2+2+1 ++2+2+1+2 ++2+3++2+ +22++2+3+ ++3++22+1 +3+3+++3+ ++2+110++
output:
\\/\//\\ \\/\//\\ /\/\//\\ \\/\/\\/ \\/\\\\/ \\////// \\\/\\\/ /\////\\
result:
ok 8 lines
Test #32:
score: 0
Accepted
time: 5ms
memory: 3604kb
input:
8 +++++++++ +33++3+3+ +++++33++ ++3+++++1 +3+3+++2+ ++3+1+32+ +++2+3+31 +1+++23++ +11+1+1++
output:
\\//\/// /\\\\\/\ \\///\\\ \\\//\\\ /\//\\// /\\\\\\\ /\///\/\ /////\\\
result:
ok 8 lines
Test #33:
score: 0
Accepted
time: 4ms
memory: 3852kb
input:
8 +++++++++ +33++23+0 ++++2++1+ ++3++3+30 +3+22+2++ ++3++22++ +3++++3+0 +3+223+2+ ++++++2+0
output:
\\//\\// /\\////\ \\/\\\// \////\/\ \\\\\\/\ \/\\\\// \\\\\\\\ /\///\//
result:
ok 8 lines
Test #34:
score: 0
Accepted
time: 10ms
memory: 3828kb
input:
8 +++++++++ ++3++2+20 +3+3+1+++ ++2+3+++2 +++++3+++ +2+2++3++ +1+1+3++1 ++3++33++ +1+1++++0
output:
\\///\// \\\\/\\\ /\/\//\\ /\/\\/// /\/\\\// /\/\\/// \\//\\// /////\\/
result:
ok 8 lines
Test #35:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
8 +++++++++ +3+1+1+22 ++22222++ +2+++++22 ++2+2+2++ +++2+3++2 +2++2+2++ +4+++3+22 +++11++++
output:
\//\/\\\ //////// \\\\\\\\ //////// \\\\\//\ \/////// \//\\\\\ /\///\//
result:
ok 8 lines
Test #36:
score: 0
Accepted
time: 52ms
memory: 4884kb
input:
8 +++++++++ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +0+0+0+0+
output:
/\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\ /\/\/\/\
result:
ok 8 lines
Test #37:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
8 +0+0+0+0+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +2+2+2+2+ +++++++++
output:
\/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/ \/\/\/\/
result:
ok 8 lines
Test #38:
score: 0
Accepted
time: 4ms
memory: 3724kb
input:
8 +++++++++ +22222220 +++++++++ +22222220 +++++++++ +22222220 +++++++++ +22222220 +++++++++
output:
//////// \\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\
result:
ok 8 lines
Test #39:
score: 0
Accepted
time: 3ms
memory: 3564kb
input:
8 +++++++++ 02222222+ +++++++++ 02222222+ +++++++++ 02222222+ +++++++++ 02222222+ +++++++++
output:
\\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\ //////// \\\\\\\\ ////////
result:
ok 8 lines