QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#706210#2898. DiagonalsniwradTL 22ms3980kbC++143.8kb2024-11-03 09:21:472024-11-03 09:21:47

Judging History

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

  • [2024-11-03 09:21:47]
  • 评测
  • 测评结果:TL
  • 用时:22ms
  • 内存:3980kb
  • [2024-11-03 09:21:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int sz = (n + 1) * (n + 1);
    vector<int> arr(sz);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            char c;
            cin >> c;
            if (c == '+') {
                arr[i * (n + 1) + j] = -1;
            } else {
                arr[i * (n + 1) + j] = c - '0';
            }
        }
    }
    string sol = "";
    queue<string> q;
    q.push("0");
    q.push("1");
    while(q.size() > 0) {
        int i = q.front().size() - 1;
        int row = i / n;
        int col = i % n;
        int tl = row * (n + 1) + col;
        int tr = tl + 1;
        int bl = tl + n + 1;
        int br = bl + 1;
        vector<int> count(br + 1);
        vector<vector<int>> graph(br + 1);
        for (int i = 0; i < q.front().size() - 1; i++) {
            int row = i / n;
            int col = i % n;
            int tl = row * (n + 1) + col;
            int tr = tl + 1;
            int bl = tl + n + 1;
            int br = bl + 1;
            if (q.front()[i] == '0') {
                count[tl]++;
                count[br]++;
                graph[tl].push_back(br);
                graph[br].push_back(tl);
            } else {
                count[tr]++;
                count[bl]++;
                graph[tr].push_back(bl);
                graph[bl].push_back(tr);
            }
        }
        if (q.front()[i] == '0') {
            count[tl]++;
            count[br]++;
        } else {
            count[tr]++;
            count[bl]++;
        }
        if (arr[tl] != -1 && count[tl] != arr[tl]) {
            q.pop();
            continue;
        }
        if (arr[tr] != -1 && count[tr] > arr[tr]) {
            q.pop();
            continue;
        }
        if (arr[bl] != -1 && count[bl] > arr[bl]) {
            q.pop();
            continue;
        }
        if (arr[br] != -1 && count[br] > arr[br]) {
            q.pop();
            continue;
        }
        if (col == n - 1 && arr[tr] != -1 && count[tr] != arr[tr]) {
            q.pop();
            continue;
        }
        if (row == n - 1 && arr[bl] != -1 && count[bl] != arr[bl]) {
            q.pop();
            continue;
        }
        if (q.front()[i] == '1') {
            queue<int> bfs;
            vector<int> vis(sz);
            vis[bl] = 1;
            bfs.push(bl);
            while(bfs.size() > 0) {
                for (int node : graph[bfs.front()]) {
                    if (vis[node] == 0) {
                        bfs.push(node);
                        vis[node] = 1;
                    }
                }
                bfs.pop();
            }
            if (vis[tr] == 1) {
                q.pop();
                continue;
            }
        }
        if (q.front().size() == n * n) {
            if (arr[tr] != -1 && count[tr] != arr[tr]) {
                q.pop();
                continue;
            }
            if (arr[bl] != -1 && count[bl] != arr[bl]) {
                q.pop();
                continue;
            }
            if (arr[br] != -1 && count[br] != arr[br]) {
                q.pop();
                continue;
            }
            sol = q.front();
            break;
        }
        q.push(q.front() + '0');
        q.push(q.front() + '1');
        q.pop();
    }
    if (sol.size() < n * n) {
        cout << sol.size() << "\n";
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (sol[i * n + j] == '0') {
                cout << "\\";
            } else {
                cout << "/";
            }
        }
        cout << "\n";
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 22ms
memory: 3980kb

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: 13ms
memory: 3608kb

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: 12ms
memory: 3920kb

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: 0ms
memory: 3660kb

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: 0ms
memory: 3572kb

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: 3564kb

input:

5
++1+++
12+++1
+2121+
+2+22+
+323++
++++1+

output:

////\
////\
\\///
\\///
/\/\\

result:

ok 5 lines

Test #7:

score: -100
Time Limit Exceeded

input:

8
+++++++++
++4+++22+
+3+++3+3+
++++2+3++
++1++++21
++21++3++
+2+++++21
+4+1+2+11
++++2+1+0

output:


result: