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

Code

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

static constexpr long mod = pow(10, 9) + 7;

constexpr int8_t A = 1, B = 2;

unsigned long count(unsigned int row, unsigned int n, vector<vector<char>>& t,
		vector<int8_t>& rowd, vector<int8_t>& cold) {
	if (!(rowd[row] & A)) {
		unsigned long r = 0;
		for (unsigned int j = 0; j < n; j++) {
			if (t[row][j] != '.' || (cold[j] & A)) continue;
			t[row][j] = 'A';
			rowd[row] |= A;
			cold[j] |= A;
			r += count(row, n, t, rowd, cold);
			r %= mod;
			t[row][j] = '.';
			rowd[row] ^= A;
			cold[j] ^= A;
		}
		return r;
	} else if (!(rowd[row] & B)) {
		unsigned long r = 0;
		for (unsigned int j = 0; j < n; j++) {
			if (t[row][j] != '.' || (cold[j] & B)) continue;
			t[row][j] = 'B';
			rowd[row] |= B;
			cold[j] |= B;
			r += count(row, n, t, rowd, cold);
			r %= mod;
			t[row][j] = '.';
			rowd[row] ^= B;
			cold[j] ^= B;
		}
		return r;
	} else if (row < n - 1)
		return count(row + 1, n, t, rowd, cold);
	else return 1;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	unsigned int n;
	cin >> n;
	vector<vector<char>> t(n);
	for (unsigned int i = 0; i < n; i++) {
		t[i] = vector<char>(n);
		for (unsigned int j = 0; j < n; j++)
			cin >> t[i][j];
	}
	vector<int8_t> rowd(n);
	for (unsigned int i = 0; i < n; i++) {
		int8_t bits = 0;
		for (unsigned int j = 0; j < n; j++) {
			if (t[i][j] == 'A') bits |= A;
			else if (t[i][j] == 'B') bits |= B;
		}
		rowd[i] = bits;
	}
	vector<int8_t> cold(n);
	for (unsigned int j = 0; j < n; j++) {
		int8_t bits = 0;
		for (unsigned int i = 0; i < n; i++) {
			if (t[i][j] == 'A') bits |= A;
			else if (t[i][j] == 'B') bits |= B;
		}
		cold[j] = bits;
	}

//	cout << "rowd\n";
//	for (unsigned int i = 0; i < n; i++)
//		cout << (int) rowd[i] << '\n';
//	cout << "cold\n";
//	for (unsigned int i = 0; i < n; i++)
//		cout << (int) cold[i] << ' ';
//	cout << '\n';

	cout << count(0, n, t, rowd, cold) << '\n';
	return 0;
}

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:

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

correct output
306442892

user output
(empty)

Test 12

Group: 2

Verdict:

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

correct output
694861480

user output
(empty)

Test 13

Group: 2

Verdict:

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

correct output
555319110

user output
(empty)

Test 14

Group: 2

Verdict:

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

correct output
108372237

user output
(empty)

Test 15

Group: 2

Verdict:

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

correct output
259107857

user output
(empty)

Test 16

Group: 2

Verdict:

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

correct output
19906314

user output
(empty)

Test 17

Group: 2

Verdict:

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

correct output
224313667

user output
(empty)

Test 18

Group: 2

Verdict:

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

correct output
929574601

user output
(empty)

Test 19

Group: 2

Verdict:

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

correct output
600226043

user output
(empty)

Test 20

Group: 2

Verdict:

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

correct output
198353194

user output
(empty)

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