CSES - Datatähti 2019 alku - Results
Submission details
Task:Ruudukko
Sender:Nanohenry
Submission time:2018-10-13 18:48:58 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#20.02 s1details
#30.01 s1details
#4ACCEPTED0.02 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.02 s1details
#70.01 s1details
#80.03 s1details
#9ACCEPTED0.01 s1details
#100.02 s1details
#11--2details
#12--2details
#13--2details
#14--2details
#15--2details
#16--2details
#17--2details
#18--2details
#19--2details
#20--2details
#210.34 s3details
#220.34 s3details
#230.03 s3details
#240.04 s3details
#250.02 s3details
#26--3details
#270.35 s3details
#280.03 s3details
#290.02 s3details
#300.03 s3details

Code

#include <iostream>
#include <string>

#define MOD 1000000007

using namespace std;

struct uint512_t {
    uint64_t hhh, hhl, hlh, hll, lhh, lhl, llh, lll;
    uint512_t() : hhh(0), hhl(0), hlh(0), hll(0), lhh(0), lhl(0), llh(0), lll(0) {}
    uint512_t(uint64_t a) : hhh(0), hhl(0), hlh(0), hll(0), lhh(0), lhl(0), llh(0), lll(a) {}
    uint512_t(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e, uint64_t f, uint64_t g, uint64_t h) : hhh(a), hhl(b), hlh(c), hll(d), lhh(e), lhl(f), llh(g), lll(h) {}
    inline void operator=(const uint512_t &o) {
        hhh = o.hhh;
        hhl = o.hhl;
        hlh = o.hlh;
        hll = o.hll;
        lhh = o.lhh;
        lhl = o.lhl;
        llh = o.llh;
        lll = o.lll;
    }
    inline void set(long i) {
        if (i < 64) {
            lll |= 1 << (i % 64);
        } else if (i < 64 * 2) {
            llh |= 1 << (i % 64);
        } else if (i < 64 * 3) {
            lhl |= 1 << (i % 64);
        } else if (i < 64 * 4) {
            lhh |= 1 << (i % 64);
        } else if (i < 64 * 5) {
            hll |= 1 << (i % 64);
        } else if (i < 64 * 6) {
            hlh |= 1 << (i % 64);
        } else if (i < 64 * 7) {
            hhl |= 1 << (i % 64);
        } else {
            hhh |= 1 << (i % 64);
        }
    }
    inline bool operator==(const uint512_t &o) {
        return hhh == o.hhh && hhl == o.hhl && hlh == o.hlh && hll == o.hll && lhh == o.lhh && lhh == o.lhh && lhl == o.lhl && llh == o.llh && lll == o.lll;
    }
    inline uint512_t operator~() {
        return uint512_t(~hhh, ~hhl, ~hlh, ~hll, ~lhh, ~lhl, ~llh, ~lll);
    }
    inline uint512_t operator-() {
        uint64_t a = ~lll + 1ULL;
        uint64_t b = ~llh + (a == 0);
        uint64_t c = ~llh + (b == 0);
        uint64_t d = ~llh + (c == 0);
        uint64_t e = ~llh + (d == 0);
        uint64_t f = ~llh + (e == 0);
        uint64_t g = ~llh + (f == 0);
        uint64_t h = ~llh + (g == 0);
        return uint512_t(h, g, f, e, d, c, b, a);
    }
    inline uint512_t operator&(const uint512_t &o) {
        return uint512_t(hhh & o.hhh, hhl & o.hhl, hlh & o.hlh, hll & o.hll, lhh & o.lhh, lhl & o.lhl, llh & o.llh, lll & o.lll);
    }
    inline uint512_t operator|(const uint512_t &o) {
        return uint512_t(hhh | o.hhh, hhl | o.hhl, hlh | o.hlh, hll | o.hll, lhh | o.lhh, lhl | o.lhl, llh | o.llh, lll | o.lll);
    }
    inline operator bool() {
        return hhh | hhl | hlh | hll | lhh | lhl | llh | lll;
    }
    inline long popcount() {
        return __builtin_popcount(lll) + __builtin_popcount(llh) + __builtin_popcount(lhl) + __builtin_popcount(lhh) + __builtin_popcount(hll) + __builtin_popcount(hlh) + __builtin_popcount(hhl) + __builtin_popcount(hhh);
    }
    inline operator string() {
        string res = "";
        for (long i = 63; i >= 0; i--) {
            if (lll & (1ULL << i)) {
                res += '1';
            } else {
                res += '0';
            }
        }
        return res;
    }
};

long n, r;
string t[500];
uint512_t m;
uint64_t g[8];

void search(uint512_t a, uint512_t b) {
    //cout << string(a) << '\t' << string(b) << '\n';
    if (a == m && b == m) {
        r = (r + 1) % MOD;
        return;
    }
    if (a.popcount() == 1 && b.popcount() == 1 && a == b) {
        return;
    }
    uint512_t p1 = ~a & m;
    while (p1) {
        uint512_t b1 = p1 & -p1;
        p1 = p1 & ~b1;
        uint512_t p2 = ~(b | b1) & m;
        while (p2) {
            uint512_t b2 = p2 & -p2;
            p2 = p2 & ~b2;
            search(a | b1, b | b2);
        }
    }
}

int main() {
    cin >> n;
    for (long i = 0; i < n; i++) {
        cin >> t[i];
    }
    g[n / 64] = (1 << (n % 64)) - 1;
    for (long i = n / 64 - 1; i >= 0; i--) {
        g[i] = ~g[i];
    }
    m = uint512_t(g[7], g[6], g[5], g[4], g[3], g[2], g[1], g[0]);
    uint512_t a, b;
    for (long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            if (t[i][j] == 'A') {
                a.set(j);
            } else if (t[i][j] == 'B') {
                b.set(j);
            }
        }
    }
    search(a, b);
    cout << r << '\n';
    //system("pause");
}

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
0

Test 3

Group: 1

Verdict:

input
2
B.
.A

correct output
0

user output
1

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
0

Test 8

Group: 1

Verdict:

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

correct output
22

user output
0

Test 9

Group: 1

Verdict: ACCEPTED

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

correct output
2

user output
2

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
(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
0

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
(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
0

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