CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:jarvenp
Submission time:2018-10-02 22:00:46 +0300
Language:C++
Status:READY
Result:31
Feedback
groupverdictscore
#1ACCEPTED31
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.03 s1details
#3ACCEPTED0.01 s1details
#4ACCEPTED0.01 s1details
#5ACCEPTED0.03 s1details
#6ACCEPTED0.02 s1details
#7ACCEPTED0.01 s1details
#8ACCEPTED0.02 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.03 s1details
#11--2details
#12--2details
#130.02 s2details
#140.01 s2details
#150.02 s2details
#160.02 s2details
#170.02 s2details
#180.02 s2details
#190.02 s2details
#200.02 s2details
#210.01 s3details
#220.03 s3details
#230.03 s3details
#240.02 s3details
#250.02 s3details
#260.03 s3details
#270.02 s3details
#280.02 s3details
#290.01 s3details
#300.02 s3details

Code

#include <bits/stdc++.h>
#include <stdint.h>
using namespace std;
uint32_t n;
uint64_t counter;
const uint64_t M = 1e9+7;
uint64_t sum(uint32_t amount, uint32_t size){
if(amount == 1){
return size;
}
uint64_t ans = 0;
uint32_t temp = size-1;
while(amount-1 <= temp){
ans += sum(amount-1, temp);
temp--;
}
return ans;
}
uint64_t fact(uint32_t val){
uint64_t ans=1;
for(uint32_t i=1; i<=val; i++){
ans *= i;
ans %=M;
}
return ans;
}
void taulukot(uint32_t layer, char taul[][100], char goal[][100], uint16_t aUsed, uint16_t bUsed){
if(layer == n){
bool match = true;
for(uint32_t i=0; i<n; i++){
// cout << taul[i]<<"\n";
for(uint32_t i2=0; i2<n; i2++){
if((taul[i][i2] != goal[i][i2]) && (goal[i][i2] != '.')){
match = false;
break;
}
}
if(!match){
break;
}
}
if(match){
counter++;
}
// cout << "\n";
}
else{
char temp[100][100];
for(uint32_t i=0; i<n; i++){
for(uint32_t i2=0; i2<n; i2++){
temp[i][i2] = taul[i][i2];
}
temp[i][n] = 0;
}
for(uint32_t i=0; i<n; i++){
//cout <<"b\n";
if(((aUsed>>i)&1) == 0){
//cout << "a\n";
aUsed = aUsed | (1<<i);
temp[layer][i] = 'A';
for(uint32_t i2=0; i2<n; i2++){
if((((bUsed>>i2)&1) == 0) && (i2 != i)){
// cout << i<<" "<<temp[layer][i]<<"\n";
bUsed = bUsed | (1<<i2);
temp[layer][i2] = 'B';
taulukot(layer+1, temp, goal, aUsed, bUsed);
bUsed = bUsed & ~(1<<i2);
temp[layer][i2] = '.';
}
}
aUsed = aUsed & ~(1<<i);
temp[layer][i] = '.';
}
}
}
}
int main(){
cin >> n;
char goal[100][100];
for(uint32_t i=0; i<n; i++){
cin >> goal[i];
}
/*
uint64_t ans = (fact(n-1)-1)*(sum(1,n))%M;
for(uint32_t i=2; i<(n-1); i++){
uint64_t temp = ((fact(n-i)-1)*sum(i,n))%M;
if(temp > ans){
ans += M;
}
ans-= temp;
}
ans+= 1;
ans = ((fact(n)-ans)*fact(n))%M;
cout << ans<<"\n";*/
char taul[100][100];
for(uint32_t i=0; i<n; i++){
for(uint32_t i2=0; i2<n; i2++){
taul[i][i2] = '.';
}
taul[i][n] = 0;
}
counter = 0;
taulukot(0,taul,goal,0,0);
cout << counter<<"\n";
}

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)

Error:
*** stack smashing detected ***: <unknown> terminated

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:

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

correct output
2

user output
(empty)

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:

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

correct output
2196

user output
(empty)

Test 30

Group: 3

Verdict:

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

correct output
1

user output
(empty)