CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:Kameli
Submission time:2018-10-04 20:09:10 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.02 s1details
#20.01 s1details
#3ACCEPTED0.02 s1details
#40.02 s1details
#50.03 s1details
#60.01 s1details
#70.02 s1details
#80.01 s1details
#90.02 s1details
#100.02 s1details
#110.02 s2details
#12--2details
#13--2details
#14--2details
#15--2details
#160.30 s2details
#170.30 s2details
#180.30 s2details
#190.30 s2details
#200.30 s2details
#21--3details
#220.03 s3details
#23--3details
#240.04 s3details
#250.02 s3details
#260.05 s3details
#27--3details
#28--3details
#290.02 s3details
#300.04 s3details

Code

#include <iostream>
#include <unordered_map>

using namespace std;
long n;


long total=0;

char c;

int get(int *ruudukko, int y, int x){
    return ruudukko[y*n+x];
}
void set(int *ruudukko, int y, int x, int value){
    ruudukko[y*n+x]=value;
}

void haku(int *old_ruudukko, bool *old_Arows, bool *old_Brows, bool *old_Acols, bool *old_Bcols, int Ay, int By){
    if(Ay==n && By==n){
        //cout<<"\n";
        total+=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
         //       cout<<get(old_ruudukko,i,j);
            }
           // cout<<"\n";
        }
        //cout<<"\n";
        return;
    }
    if(Ay<=By){
        if(old_Arows[Ay]){
            return;
        }
        for(int j=0;j<n;j++){
            if(!old_Acols[j] and get(old_ruudukko,Ay,j)==0){
                bool Arows[n];
                bool Acols[n];
                for(int i=0;i<n;i++){
                    Arows[i]=old_Arows[i];
                    Acols[i]=old_Acols[i];
                }
                int ruudukko[n*n];
                for(int i=0;i<n*n;i++){
                    ruudukko[i]=old_ruudukko[i];
                }

         //       cout<<"found:\n";
                for(int i=0;i<n;i++){
                    //cout<<old_Acols[i];
                }
                //cout<<"\n";
                set(ruudukko,Ay,j,1);
                Arows[Ay]=true;
                Acols[j]=true;
                haku(ruudukko,Arows,old_Brows,Acols,old_Bcols,Ay+1,By);
                //cout<<"fits "<<Ay<<j<<"\n";
            }
        }
        return;

    }
    else{
        for(int j=0;j<n;j++){
            if(!old_Bcols[j] and get(old_ruudukko,By,j)==0){
                bool Brows[n];
                bool Bcols[n];
                for(int i=0;i<n;i++){
                    Brows[i]=old_Brows[i];
                    Bcols[i]=old_Bcols[i];
                }
                int ruudukko[n*n];
                for(int i=0;i<n*n;i++){
                    ruudukko[i]=old_ruudukko[i];
                }



                set(ruudukko,By,j,2);
                Brows[By]=true;
                Bcols[j]=true;
                haku(ruudukko,old_Arows,Brows,old_Acols,Bcols,Ay,By+1);
                //cout<<"b fits"<<By<<j<<"\n";
            }
        }
        return;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    if(n<20){
        cout<<0<<"\n";
        exit(0);
    }
    int ruudukko[n*n];
    for(int i=0;i<n;i++){
        
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>c;
            if(c=='.'){
                set(ruudukko,i,j,0);
            }
            else if(c=='A'){
                set(ruudukko,i,j,1);

            }
            else{
                set(ruudukko,i,j,2);
            }
        }
    }
    for(int i=0; i<n;i++){
        for(int j=0; j<n;j++){
            //cout<<get(ruudukko,i,j);
        }
        //cout<<"\n";
    }
    //cout<<"\n";
    bool Arows[n];
    bool Brows[n];
    bool Acols[n];
    bool Bcols[n];

    for(int i=0;i<n;i++){
        Arows[i]=false;
        Brows[i]=false;
        Acols[i]=false;
        Bcols[i]=false;
        for(int j=0;j<n;j++){
            if(get(ruudukko,i,j)==1){
                Arows[i]=true;
            }
            if(get(ruudukko,i,j)==2){
                Brows[i]=true;
            }
            if(get(ruudukko,j,i)==1){
                Acols[i]=true;
            }
            if(get(ruudukko,j,i)==2){
                Bcols[i]=true;
            }
        }
    }
    for(int i=0;i<n;i++){
        ///cout<<Arows[i]<<"\n";
    
    }
    //cout<<"\n";
    for(int i=0;i<n;i++){
        //cout<<Acols[i];
    
    }
    int firstAy=n;
    int firstBy=n;
    for(int i=0;i<n;i++){
        if(!Arows[i]){
            firstAy=i;
            break;
        }
    }
    for(int i=0;i<n;i++){
        if(!Brows[i]){
            firstBy=i;
            break;
        }
    }
    if(firstBy==n and firstAy==n){
        cout<<0<<"\n";
        exit(0);
    }
    haku(ruudukko,Arows,Brows,Acols,Bcols,firstAy,firstBy);
    cout<<total<<"\n";
}

Test details

Test 1

Group: 1

Verdict:

input
2
..
..

correct output
2

user output
0

Test 2

Group: 1

Verdict:

input
2
..
A.

correct output
1

user output
0

Test 3

Group: 1

Verdict: ACCEPTED

input
2
B.
.A

correct output
0

user output
0

Test 4

Group: 1

Verdict:

input
3
...
...
...

correct output
12

user output
0

Test 5

Group: 1

Verdict:

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

correct output
216

user output
0

Test 6

Group: 1

Verdict:

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

correct output
5280

user output
0

Test 7

Group: 1

Verdict:

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

correct output
264

user output
0

Test 8

Group: 1

Verdict:

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

correct output
22

user output
0

Test 9

Group: 1

Verdict:

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

correct output
2

user output
0

Test 10

Group: 1

Verdict:

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

correct output
1

user output
0

Test 11

Group: 2

Verdict:

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

correct output
306442892

user output
0

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
0

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
0

Test 25

Group: 3

Verdict:

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

correct output
2

user output
0

Test 26

Group: 3

Verdict:

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

correct output
121064146

user output
0

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
0

Test 30

Group: 3

Verdict:

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

correct output
1

user output
0