QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30012#2898. DiagonalsGeorge_PloverAC ✓52ms4884kbC++6.2kb2022-04-24 02:51:182022-04-28 12:18:43

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-28 12:18:43]
  • 评测
  • 测评结果:AC
  • 用时:52ms
  • 内存:4884kb
  • [2022-04-24 02:51:18]
  • 提交

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