CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:SMemsky
Submission time:2018-10-14 19:40:56 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#20.02 s1details
#30.02 s1details
#4ACCEPTED0.01 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.02 s1details
#70.02 s1details
#80.01 s1details
#90.01 s1details
#100.03 s1details
#11ACCEPTED0.01 s2details
#12ACCEPTED0.02 s2details
#13ACCEPTED0.02 s2details
#14ACCEPTED0.02 s2details
#150.02 s2details
#160.02 s2details
#170.02 s2details
#18ACCEPTED0.03 s2details
#190.02 s2details
#200.02 s2details
#210.02 s3details
#220.02 s3details
#230.04 s3details
#240.03 s3details
#250.02 s3details
#260.02 s3details
#270.04 s3details
#280.03 s3details
#290.03 s3details
#300.02 s3details

Code

#include <cassert>
#include <iostream>
#include <vector>
#include <random>

const uint64_t modulo = 1000000007;

uint64_t solutionCounter = 0;

// Memoize?
std::vector<uint64_t> factorialBuffer = {1};
std::vector<uint64_t> derangementBuffer = {0, 1, 1, 2, 9};

uint64_t factMod(uint64_t n) {
    if (n >= modulo) {
        return 0;
    }
    for (uint64_t i = factorialBuffer.size(); i <= n; ++i) {
        factorialBuffer.push_back((factorialBuffer[i-1] * i) % modulo);
    }
    return factorialBuffer[n];
}

uint64_t derMod(uint64_t n) {
    if (n < 2) {
        assert(false);
    }
    for (uint64_t i = derangementBuffer.size(); i <= n; ++i) {
        derangementBuffer.push_back(((i-1) % modulo) * ((derangementBuffer[i-1] + derangementBuffer[i-2]) % modulo));
    }
    return derangementBuffer[n];
}

uint64_t countEmpty(uint64_t n) {
    return (derMod(n) * factMod(n)) % modulo;
}

bool rowHasA(std::vector<uint8_t> const & field, uint64_t n, uint64_t row) {
    for (uint64_t x = 0; x < n; ++x) {
        if (field[row*n + x] == 1) { return true; }
    }
    return false;
}

bool rowHasB(std::vector<uint8_t> const & field, uint64_t n, uint64_t row) {
    for (uint64_t x = 0; x < n; ++x) {
        if (field[row*n + x] == 2) { return true; }
    }
    return false;
}

bool colHasA(std::vector<uint8_t> const & field, uint64_t n, uint64_t col) {
    for (uint64_t y = 0; y < n; ++y) {
        if (field[y*n + col] == 1) { return true; }
    }
    return false;
}

bool colHasB(std::vector<uint8_t> const & field, uint64_t n, uint64_t col) {
    for (uint64_t y = 0; y < n; ++y) {
        if (field[y*n + col] == 2) { return true; }
    }
    return false;
}

char keks[] = {'0','A','B'};

void printField(std::vector<uint8_t> const & field, uint64_t n) {
    std::cout << std::endl;
    for (uint64_t y = 0; y < n; ++y) {
        for (uint64_t x = 0; x < n; ++x) {
            std::cout << keks[field[y*n+x]] << " ";
        }
        std::cout << std::endl;
    }
}

uint64_t recursiveCounter(std::vector<uint8_t> field, uint64_t n) {
    uint64_t row = 0;
    bool hasA = false;
    bool hasB = false;
    do {
        hasA = rowHasA(field, n, row);
        hasB = rowHasB(field, n, row);
        ++row;
    } while (hasA == true && hasB == true && row < n);
    --row;

    if (hasA && hasB) {
        // std::cout << "Well done, we finished" << std::endl;
        if (solutionCounter > 0 && field[(n-1)*n+1] != 0) {
            --solutionCounter;
            printField(field, n);
        }
        assert(row == n-1);
        return 1;
    }

    uint64_t sum = 0;
    if (!hasA) {
        for (uint64_t x = 0; x < n; ++x) {
            if (field[row*n + x] == 0 && !colHasA(field, n, x)) {
                field[row*n + x] = 1;
                // std::cout << "Placing A at row " << row+1 << ", col " << x+1 << std::endl;
                sum += recursiveCounter(field, n);
                // sum %= modulo;
                field[row*n + x] = 0;
            }
        }

        return sum;
    }
    if (!hasB) {
        for (uint64_t x = 0; x < n; ++x) {
            if (field[row*n + x] == 0 && !colHasB(field, n, x)) {
                field[row*n + x] = 2;
                // std::cout << "Placing B at row " << row+1 << ", col " << x+1 << std::endl;
                sum += recursiveCounter(field, n);
                // sum %= modulo;
                field[row*n + x] = 0;
            }
        }

        return sum;
    }

    assert(false);
}

int main() {
    uint64_t n = 0;
    std::cin >> n;
    std::vector<uint8_t> field(n * n);
    for (uint64_t y = 0; y < n; ++y) {
        std::string rowString = "";
        std::cin >> rowString;
        for (uint64_t x = 0; x < n; ++x) {
            if (rowString[x] == 'A') {
                field[y * n + x] = 1;
            } else if (rowString[x] == 'B') {
                field[y * n + x] = 2;
            }
        }
    }

    std::cout << countEmpty(n) << std::endl;

    // if (field == std::vector<uint8_t>(n*n)) {
    //     std::cout << countEmpty(n) << std::endl;
    // } else {
    //     std::cout << recursiveCounter(field, n) << std::endl;
    // }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2
..
..

correct output
2

user output
2

Test 2

Group: 1

Verdict:

input
2
..
A.

correct output
1

user output
2

Test 3

Group: 1

Verdict:

input
2
B.
.A

correct output
0

user output
2

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:

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

correct output
264

user output
5280

Test 8

Group: 1

Verdict:

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

correct output
22

user output
5280

Test 9

Group: 1

Verdict:

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

correct output
2

user output
5280

Test 10

Group: 1

Verdict:

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

correct output
1

user output
5280

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:

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

correct output
259107857

user output
512075847

Test 16

Group: 2

Verdict:

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

correct output
19906314

user output
108186295

Test 17

Group: 2

Verdict:

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

correct output
224313667

user output
400873629

Test 18

Group: 2

Verdict: ACCEPTED

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

correct output
929574601

user output
929574601

Test 19

Group: 2

Verdict:

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

correct output
600226043

user output
853194033

Test 20

Group: 2

Verdict:

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

correct output
198353194

user output
45537138

Test 21

Group: 3

Verdict:

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

correct output
840243733

user output
853194033

Test 22

Group: 3

Verdict:

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

correct output
4146290

user output
853194033

Test 23

Group: 3

Verdict:

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

correct output
173518884

user output
853194033

Test 24

Group: 3

Verdict:

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

correct output
20044800

user output
853194033

Test 25

Group: 3

Verdict:

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

correct output
2

user output
853194033

Test 26

Group: 3

Verdict:

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

correct output
121064146

user output
45537138

Test 27

Group: 3

Verdict:

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

correct output
848435259

user output
45537138

Test 28

Group: 3

Verdict:

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

correct output
296240911

user output
45537138

Test 29

Group: 3

Verdict:

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

correct output
2196

user output
45537138

Test 30

Group: 3

Verdict:

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

correct output
1

user output
45537138