CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:Jaahas
Submission time:2018-10-14 00:21:56 +0300
Language:Java
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED31
#2ACCEPTED14
#30
Test results
testverdicttimegroup
#1ACCEPTED0.22 s1details
#2ACCEPTED0.22 s1details
#3ACCEPTED0.23 s1details
#4ACCEPTED0.23 s1details
#5ACCEPTED0.21 s1details
#6ACCEPTED0.22 s1details
#7ACCEPTED0.22 s1details
#8ACCEPTED0.22 s1details
#9ACCEPTED0.22 s1details
#10ACCEPTED0.22 s1details
#11ACCEPTED0.22 s2details
#12ACCEPTED0.23 s2details
#13ACCEPTED0.25 s2details
#14ACCEPTED0.27 s2details
#15ACCEPTED0.29 s2details
#16ACCEPTED0.31 s2details
#17ACCEPTED0.31 s2details
#18ACCEPTED0.32 s2details
#19ACCEPTED0.32 s2details
#20ACCEPTED0.32 s2details
#21--3details
#22--3details
#23--3details
#24--3details
#25ACCEPTED0.32 s3details
#26--3details
#27--3details
#28--3details
#29ACCEPTED0.36 s3details
#30ACCEPTED0.32 s3details

Code

//package com.tuomas;
import java.util.*;

public class Ruudukko {
    static int c = 0;
    static int n = 0;
    static char[][] ruudukko;
    static char[][] ruudukko2;
    static boolean[] ai;
    static boolean[] aj;
    static boolean[] bi;
    static boolean[] bj;
    static final long MOD = 1000000007;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt();
        ruudukko = new char[n][n];
        ruudukko2 = new char[n][n];
        ai = new boolean[n];
        aj = new boolean[n];
        bi = new boolean[n];
        bj = new boolean[n];
        long count = 0;
        for (int i = 0; i < n; i++) {
            String string = input.next();
            for (int j = 0; j < n; j++) {
                ruudukko[i][j] = string.charAt(j);
                if(ruudukko[i][j] == 'A') {
                    count++;
                    ai[i] = true;
                    aj[j] = true;
                } else if(ruudukko[i][j] == 'B') {
                    count++;
                    bi[i] = true;
                    bj[j] = true;
                }
            }
        }
        if(count == 0) {
            long result = (factorial(n) * (n - 1)) % MOD;
            result = (result * f(n - 2)) % MOD;
            System.out.println(result);
        } else {
            hakua(0);
            System.out.println(c);
        }

    }

    static void hakua(int i) {
        if(i >= n) {
            hakub(0);
            return;
        } else if(ai[i]) {
            hakua(i + 1);
        } else {
            for (int j = 0; j < n; j++) {
                if(ruudukko[i][j] == '.') {
                    if(aj[j]) {
                        continue;
                    }
                    aj[j] = true;
                    ruudukko[i][j] = 'A';
                    hakua(i + 1);
                    aj[j] = false;
                    ruudukko[i][j] = '.';
                }
            }
        }
    }

    static void hakub(int i) {
        if(i >= n) {
            c = (c + 1) % (int)MOD;
            return;
        } else if(bi[i]) {
            hakub(i + 1);
        } else {
            for (int j = 0; j < n; j++) {
                if(ruudukko[i][j] == '.') {
                    if(bj[j]) {
                        continue;
                    }
                    bj[j] = true;
                    hakub(i + 1);
                    bj[j] = false;
                }
            }
        }
    }

    public static long factorial(int n) {
        long result = 1;

        for (long factor = 2; factor <= n; factor++) {
            result = (result * factor) % MOD;
        }

        return result;
    }

    public static long f(long n) {
        if (n <= 1) {
            return 1;
        } else {
            long r1 = 1;
            long r2 = 1;
            for(long i = 2; i <= n; i++) {
                long temp = r2;
                r2 = ((r2 * i)%MOD + (r1 * (i-1))%MOD)%MOD;
                r1 = temp;
            }
            return r2;
        }
    }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2
..
..

correct output
2

user output
2

Test 2

Group: 1

Verdict: ACCEPTED

input
2
..
A.

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
2
B.
.A

correct output
0

user output
0

Test 4

Group: 1

Verdict: ACCEPTED

input
3
...
...
...

correct output
12

user output
12

Test 5

Group: 1

Verdict: ACCEPTED

input
4
....
....
....
....

correct output
216

user output
216

Test 6

Group: 1

Verdict: ACCEPTED

input
5
.....
.....
.....
.....
...

correct output
5280

user output
5280

Test 7

Group: 1

Verdict: ACCEPTED

input
5
....A
.....
.....
.....
...

correct output
264

user output
264

Test 8

Group: 1

Verdict: ACCEPTED

input
5
B....
.....
.....
.A.B.
...

correct output
22

user output
22

Test 9

Group: 1

Verdict: ACCEPTED

input
5
B.A..
....A
.....
A.B..
...

correct output
2

user output
2

Test 10

Group: 1

Verdict: ACCEPTED

input
5
A.B..
BA...
.B.A.
...BA
...

correct output
1

user output
1

Test 11

Group: 2

Verdict: ACCEPTED

input
10
..........
..........
..........
..........
...

correct output
306442892

user output
306442892

Test 12

Group: 2

Verdict: ACCEPTED

input
50
.................................

correct output
694861480

user output
694861480

Test 13

Group: 2

Verdict: ACCEPTED

input
111
.................................

correct output
555319110

user output
555319110

Test 14

Group: 2

Verdict: ACCEPTED

input
222
.................................

correct output
108372237

user output
108372237

Test 15

Group: 2

Verdict: ACCEPTED

input
333
.................................

correct output
259107857

user output
259107857

Test 16

Group: 2

Verdict: ACCEPTED

input
444
.................................

correct output
19906314

user output
19906314

Test 17

Group: 2

Verdict: ACCEPTED

input
497
.................................

correct output
224313667

user output
224313667

Test 18

Group: 2

Verdict: ACCEPTED

input
498
.................................

correct output
929574601

user output
929574601

Test 19

Group: 2

Verdict: ACCEPTED

input
499
.................................

correct output
600226043

user output
600226043

Test 20

Group: 2

Verdict: ACCEPTED

input
500
.................................

correct output
198353194

user output
198353194

Test 21

Group: 3

Verdict:

input
499
.................................

correct output
840243733

user output
(empty)

Test 22

Group: 3

Verdict:

input
499
........................A........

correct output
4146290

user output
(empty)

Test 23

Group: 3

Verdict:

input
499
B.........A......................

correct output
173518884

user output
(empty)

Test 24

Group: 3

Verdict:

input
499
...A....B........................

correct output
20044800

user output
(empty)

Test 25

Group: 3

Verdict: ACCEPTED

input
499
AB...............................

correct output
2

user output
2

Test 26

Group: 3

Verdict:

input
500
.................................

correct output
121064146

user output
(empty)

Test 27

Group: 3

Verdict:

input
500
.................................

correct output
848435259

user output
(empty)

Test 28

Group: 3

Verdict:

input
500
.....B........A..................

correct output
296240911

user output
(empty)

Test 29

Group: 3

Verdict: ACCEPTED

input
500
.A......B........................

correct output
2196

user output
2196

Test 30

Group: 3

Verdict: ACCEPTED

input
500
...AB............................

correct output
1

user output
1