QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72970 | #2898. Diagonals | codingsword# | TL | 1200ms | 143804kb | Java11 | 3.7kb | 2023-01-21 06:02:31 | 2023-01-21 06:02:32 |
Judging History
answer
import java.util.*;
public class c {
static int n;
static char[][] input;
static char[][] answer;
static byte[] makeDSU(int n) {
byte[] res = new byte[n];
Arrays.fill(res, (byte)-1);
return res;
}
static byte find(byte[] s, byte i) {
return s[i] < (byte)0 ? i : (s[i] = find(s, s[i]));
}
static boolean union(byte[] s, byte a, byte b) {
if ((a = find(s, a)) == (b = find(s, b))) return false;
if (s[a] == s[b]) s[a]--;
if (s[a] <= s[b]) s[b] = a;
else s[a] = b;
return true;
}
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;
}
}
return true;
}
static byte[] dsu;
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;
}
byte[] save = dsu;
byte A = (byte)(i * (n + 1) + j);
byte B = (byte)((i + 1) * (n + 1) + (j + 1));
if (find(dsu, A) != find(dsu, B)) {
dsu = Arrays.copyOf(dsu, dsu.length);
union(dsu, A, B);
answer[i][j] = '\\';
if (solve(ni, nj)) return true;
dsu = save;
}
A = (byte)(i * (n + 1) + (j + 1));
B = (byte)((i + 1) * (n + 1) + j);
if (find(dsu, A) != find(dsu, B)) {
dsu = Arrays.copyOf(dsu, dsu.length);
union(dsu, A, B);
answer[i][j] = '/';
if (solve(ni, nj)) return true;
dsu = save;
}
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();
}
dsu = makeDSU((n + 1) * (n + 1));
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: 141ms
memory: 55264kb
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: 146ms
memory: 55064kb
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: 105ms
memory: 52988kb
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: 115ms
memory: 52304kb
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: 98ms
memory: 52608kb
input:
5 +++21+ 11+2++ 1++2++ ++32+1 +3++3+ ++0+++
output:
\\/\\ \//\/ \\/\/ \//\/ //\\\
result:
ok 5 lines
Test #6:
score: 0
Accepted
time: 110ms
memory: 54976kb
input:
5 ++1+++ 12+++1 +2121+ +2+22+ +323++ ++++1+
output:
////\ ////\ \\/// \\/// /\/\\
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 761ms
memory: 138216kb
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: 96ms
memory: 53168kb
input:
1 01 10
output:
/
result:
ok single line: '/'
Test #9:
score: 0
Accepted
time: 122ms
memory: 54784kb
input:
1 0+ ++
output:
/
result:
ok single line: '/'
Test #10:
score: 0
Accepted
time: 76ms
memory: 55956kb
input:
1 10 01
output:
\
result:
ok single line: '\'
Test #11:
score: 0
Accepted
time: 96ms
memory: 53932kb
input:
1 1+ ++
output:
\
result:
ok single line: '\'
Test #12:
score: 0
Accepted
time: 107ms
memory: 54280kb
input:
1 +0 ++
output:
\
result:
ok single line: '\'
Test #13:
score: 0
Accepted
time: 117ms
memory: 54248kb
input:
1 +1 ++
output:
/
result:
ok single line: '/'
Test #14:
score: 0
Accepted
time: 119ms
memory: 54180kb
input:
1 ++ 0+
output:
\
result:
ok single line: '\'
Test #15:
score: 0
Accepted
time: 104ms
memory: 54248kb
input:
1 ++ 1+
output:
/
result:
ok single line: '/'
Test #16:
score: 0
Accepted
time: 101ms
memory: 56260kb
input:
1 ++ +0
output:
/
result:
ok single line: '/'
Test #17:
score: 0
Accepted
time: 97ms
memory: 54148kb
input:
1 ++ +1
output:
\
result:
ok single line: '\'
Test #18:
score: 0
Accepted
time: 137ms
memory: 51960kb
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: 141ms
memory: 54424kb
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: 168ms
memory: 58220kb
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: 136ms
memory: 55940kb
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: 146ms
memory: 56972kb
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: 137ms
memory: 55376kb
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: 146ms
memory: 55528kb
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: 121ms
memory: 55664kb
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: 152ms
memory: 57852kb
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: 92ms
memory: 54360kb
input:
3 ++++ +1+1 +31+ +0+0
output:
/\/ /// /\/
result:
ok 3 lines
Test #28:
score: 0
Accepted
time: 99ms
memory: 54820kb
input:
4 +++++ +3++2 ++3++ +3+3+ ++2+0
output:
\//\ \\// \\\/ /\//
result:
ok 4 lines
Test #29:
score: 0
Accepted
time: 118ms
memory: 55972kb
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: 524ms
memory: 83596kb
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: 1200ms
memory: 143796kb
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: 175ms
memory: 61680kb
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: 429ms
memory: 80096kb
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: 831ms
memory: 143804kb
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: 162ms
memory: 57872kb
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+