QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72969 | #2898. Diagonals | codingsword# | TL | 7019ms | 339060kb | Java11 | 4.5kb | 2023-01-21 05:23:03 | 2023-01-21 05:23:04 |
Judging History
answer
import java.util.*;
public class c {
static int n;
static char[][] input;
static char[][] answer;
static int countIngoing(int i, int j) {
int result = 0;
if (i < n && j < n && answer[i][j] == '\\') result += 1;
if (i > 0 && j < n && answer[i - 1][j] == '/') result += 1;
if (i < n && j > 0 && answer[i][j - 1] == '/') result += 1;
if (i > 0 && j > 0 && answer[i - 1][j - 1] == '\\') result += 1;
return result;
}
static int countPerpendicular(int i, int j) {
int result = 0;
if (i < n && j < n && answer[i][j] == '/') result += 1;
if (i > 0 && j < n && answer[i - 1][j] == '\\') result += 1;
if (i < n && j > 0 && answer[i][j - 1] == '\\') result += 1;
if (i > 0 && j > 0 && answer[i - 1][j - 1] == '/') result += 1;
return result;
}
static int countUnknown(int i, int j) {
int result = 0;
if (i < n && j < n && answer[i][j] == 0) result += 1;
if (i > 0 && j < n && answer[i - 1][j] == 0) result += 1;
if (i < n && j > 0 && answer[i][j - 1] == 0) result += 1;
if (i > 0 && j > 0 && answer[i - 1][j - 1] == 0) result += 1;
return result;
}
static boolean verify() {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
if (input[i][j] == '+') continue;
int expected = input[i][j] - '0';
int ingoing = countIngoing(i, j);
int perpen = countPerpendicular(i, j);
int unknown = countUnknown(i, j);
if (ingoing > expected) return false;
if (ingoing + unknown < expected) return false;
}
}
ArrayDeque<Integer> iq = new ArrayDeque<>();
ArrayDeque<Integer> jq = new ArrayDeque<>();
boolean[][] visited = new boolean[n + 1][n + 1];
int[][] ipar = new int[n + 1][n + 1];
int[][] jpar = new int[n + 1][n + 1];
for (int[] arr : ipar) Arrays.fill(arr, -1);
for (int[] arr : jpar) Arrays.fill(arr, -1);
for (int u = 0; u <= n; ++u) {
for (int v = 0; v <= n; ++v) {
if (visited[u][v]) continue;
iq.add(u);
jq.add(v);
visited[u][v] = true;
while (!iq.isEmpty()) {
int i = iq.poll();
int j = jq.poll();
ArrayList<Integer> ni = new ArrayList<>();
ArrayList<Integer> nj = new ArrayList<>();
if (i < n && j < n && answer[i][j] == '\\') { ni.add(i + 1); nj.add(j + 1); }
if (i > 0 && j < n && answer[i - 1][j] == '/') { ni.add(i - 1); nj.add(j + 1); }
if (i < n && j > 0 && answer[i][j - 1] == '/') { ni.add(i + 1); nj.add(j - 1); }
if (i > 0 && j > 0 && answer[i - 1][j - 1] == '\\') { ni.add(i - 1); nj.add(j - 1); }
for (int index = 0; index < ni.size(); ++index) {
int ci = ni.get(index);
int cj = nj.get(index);
if (visited[ci][cj]) {
if (ipar[i][j] == ci && jpar[i][j] == cj) {
continue;
}
return false;
}
ipar[ci][cj] = i;
jpar[ci][cj] = j;
visited[ci][cj] = true;
iq.add(ci);
jq.add(cj);
}
}
}
}
return true;
}
static boolean solve(int i, int j) {
if (!verify()) {
return false;
}
if (i == n) {
return true;
}
int ni = i, nj = j + 1;
if (nj == n) {
ni += 1;
nj = 0;
}
answer[i][j] = '\\';
if (solve(ni, nj)) return true;
answer[i][j] = '/';
if (solve(ni, nj)) return true;
answer[i][j] = 0;
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
scan.nextLine();
answer = new char[n][n];
input = new char[n + 1][];
for (int i = 0; i <= n; ++i) {
input[i] = scan.nextLine().toCharArray();
}
solve(0, 0);
for (char[] arr : answer) {
System.out.println(String.valueOf(arr));
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 303ms
memory: 75600kb
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: 295ms
memory: 74388kb
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: 188ms
memory: 61312kb
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: 105ms
memory: 53940kb
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: 138ms
memory: 54228kb
input:
5 +++21+ 11+2++ 1++2++ ++32+1 +3++3+ ++0+++
output:
\\/\\ \//\/ \\/\/ \//\/ //\\\
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 137ms
memory: 57728kb
input:
5 ++1+++ 12+++1 +2121+ +2+22+ +323++ ++++1+
output:
////\ ////\ \\/// \\/// /\/\\
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 5179ms
memory: 325436kb
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: 104ms
memory: 53800kb
input:
1 01 10
output:
/
result:
ok single line: '/'
Test #9:
score: 0
Accepted
time: 131ms
memory: 54012kb
input:
1 0+ ++
output:
/
result:
ok single line: '/'
Test #10:
score: 0
Accepted
time: 102ms
memory: 54864kb
input:
1 10 01
output:
\
result:
ok single line: '\'
Test #11:
score: 0
Accepted
time: 115ms
memory: 53904kb
input:
1 1+ ++
output:
\
result:
ok single line: '\'
Test #12:
score: 0
Accepted
time: 103ms
memory: 55928kb
input:
1 +0 ++
output:
\
result:
ok single line: '\'
Test #13:
score: 0
Accepted
time: 102ms
memory: 54296kb
input:
1 +1 ++
output:
/
result:
ok single line: '/'
Test #14:
score: 0
Accepted
time: 115ms
memory: 53932kb
input:
1 ++ 0+
output:
\
result:
ok single line: '\'
Test #15:
score: 0
Accepted
time: 118ms
memory: 56184kb
input:
1 ++ 1+
output:
/
result:
ok single line: '/'
Test #16:
score: 0
Accepted
time: 97ms
memory: 53908kb
input:
1 ++ +0
output:
/
result:
ok single line: '/'
Test #17:
score: 0
Accepted
time: 96ms
memory: 54068kb
input:
1 ++ +1
output:
\
result:
ok single line: '\'
Test #18:
score: 0
Accepted
time: 285ms
memory: 77536kb
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: 310ms
memory: 83888kb
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: 406ms
memory: 100508kb
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: 316ms
memory: 80424kb
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: 538ms
memory: 114128kb
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: 284ms
memory: 75072kb
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: 195ms
memory: 68892kb
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: 272ms
memory: 75028kb
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: 477ms
memory: 122560kb
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: 124ms
memory: 53936kb
input:
3 ++++ +1+1 +31+ +0+0
output:
/\/ /// /\/
result:
ok 3 lines
Test #28:
score: 0
Accepted
time: 121ms
memory: 55156kb
input:
4 +++++ +3++2 ++3++ +3+3+ ++2+0
output:
\//\ \\// \\\/ /\//
result:
ok 4 lines
Test #29:
score: 0
Accepted
time: 230ms
memory: 69688kb
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: 3338ms
memory: 269888kb
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: 7019ms
memory: 339060kb
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: 774ms
memory: 144576kb
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: 3299ms
memory: 227964kb
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: 5484ms
memory: 282412kb
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: 482ms
memory: 132648kb
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: -100
Time Limit Exceeded
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+