CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:ArktinenKarpalo
Submission time:2018-10-01 17:31:06 +0300
Language:C++
Status:READY
Result:45
Feedback
groupverdictscore
#1ACCEPTED31
#2ACCEPTED14
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.02 s1details
#3ACCEPTED0.01 s1details
#4ACCEPTED0.01 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.06 s1details
#7ACCEPTED0.02 s1details
#8ACCEPTED0.02 s1details
#9ACCEPTED0.02 s1details
#10ACCEPTED0.03 s1details
#11ACCEPTED0.03 s2details
#12ACCEPTED0.01 s2details
#13ACCEPTED0.02 s2details
#14ACCEPTED0.02 s2details
#15ACCEPTED0.02 s2details
#16ACCEPTED0.03 s2details
#17ACCEPTED0.02 s2details
#18ACCEPTED0.01 s2details
#19ACCEPTED0.02 s2details
#20ACCEPTED0.02 s2details
#210.01 s3details
#220.03 s3details
#230.03 s3details
#240.02 s3details
#250.02 s3details
#260.02 s3details
#270.04 s3details
#280.01 s3details
#290.01 s3details
#300.02 s3details

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<17)
#define M 1000000007
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n;
ll ans;
bool vaaka[505][2], pysty[505][2]; // 0 = A, 1 = B
string tlk[505];

void haku(int x, int y) {
	if(x == n) {
		haku(0, y+1);
		return;
	}
	if(y == n) {
		bool ok = true;
		for(int i=0; i<n; i++) {
			if(!vaaka[i][0]||!pysty[i][0]||!vaaka[i][1]||!pysty[i][1]) {
				ok = false;
				break;
			}
		}
		if(ok)
			ans++;
		return;
	}
	if(tlk[x][y] == '.') {
		if(!vaaka[y][0] && !pysty[x][0]) { // Kokeile A
			tlk[x][y] = 'A';
			vaaka[y][0] = 1;
			pysty[x][0] = 1;
			haku(x+1, y);
			tlk[x][y] = '.';
			vaaka[y][0] = 0;
			pysty[x][0] = 0;
		}
		if(!vaaka[y][1] && !pysty[x][1]) { // Kokeile B
			tlk[x][y] = 'B';
			vaaka[y][1] = 1;
			pysty[x][1] = 1;
			haku(x+1, y);
			tlk[x][y] = '.';
			vaaka[y][1] = 0;
			pysty[x][1] = 0;
		}
	}
	haku(x+1, y);
}

ll x[505], xx[505];

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> tlk[i];
	}
	if(n > 5) {
		x[0] = 1;
		xx[0] = 1;
		for(int i=1; i<=500; i++) {
			x[i] = ((i-1)*((x[i-1]+x[i-2])%M))%M;
			xx[i] = (xx[i-1]*i)%M;
		}
		cout << (x[n]*xx[n])%M;
		return 0;
	}
	// Vaaka
	for(int i=0; i<n; i++) {
		int aCnt = 0;
		int bCnt = 0;
		for(int j=0; j<n; j++) {
			if(tlk[j][i] == 'A')
				aCnt++;
			else if (tlk[j][i] == 'B')
				bCnt++;
		}
		if(aCnt > 1 || bCnt > 1) {
			cout << 0;
			return 0;
		}
		if(aCnt) {
			vaaka[i][0] = 1;
		}
		if(bCnt)
			vaaka[i][1] = 1;
	}
	// Pysty
	for(int i=0; i<n; i++) {
		int aCnt = 0;
		int bCnt = 0;
		for(int j=0; j<n; j++) {
			if(tlk[i][j] == 'A')
				aCnt++;
			else if (tlk[i][j] == 'B')
				bCnt++;
		}
		if(aCnt > 1 || bCnt > 1) {
			cout << 0;
			return 0;
		}
		if(aCnt)
			pysty[i][0] = 1;
		if(bCnt)
			pysty[i][1] = 1;
	}
	////
	haku(0, 0);
	cout << ans;
}

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
600226043

Test 22

Group: 3

Verdict:

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

correct output
4146290

user output
600226043

Test 23

Group: 3

Verdict:

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

correct output
173518884

user output
600226043

Test 24

Group: 3

Verdict:

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

correct output
20044800

user output
600226043

Test 25

Group: 3

Verdict:

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

correct output
2

user output
600226043

Test 26

Group: 3

Verdict:

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

correct output
121064146

user output
198353194

Test 27

Group: 3

Verdict:

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

correct output
848435259

user output
198353194

Test 28

Group: 3

Verdict:

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

correct output
296240911

user output
198353194

Test 29

Group: 3

Verdict:

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

correct output
2196

user output
198353194

Test 30

Group: 3

Verdict:

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

correct output
1

user output
198353194