QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#706210 | #2898. Diagonals | niwrad | TL | 22ms | 3980kb | C++14 | 3.8kb | 2024-11-03 09:21:47 | 2024-11-03 09:21:47 |
Judging History
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