QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#30011#2898. DiagonalsGeorge_PloverWA 5ms3704kbC++6.0kb2022-04-24 02:38:562022-04-28 12:18:40

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:40]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3704kb
  • [2022-04-24 02:38:56]
  • 提交

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;
}

详细

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: '///\\\\/'