CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Mariia
Submission time:2024-11-07 20:12:44 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5, 6details
#20.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#60.01 s2, 3, 4, 5, 6details
#70.00 s2, 3, 4, 5, 6details
#8ACCEPTED0.01 s2, 3, 4, 5, 6details
#90.00 s2, 3, 4, 5, 6details
#100.03 s3, 4, 5, 6details
#110.02 s3, 4, 5, 6details
#12ACCEPTED0.03 s3, 4, 5, 6details
#130.01 s3, 4, 5, 6details
#140.26 s4, 5, 6details
#150.18 s4, 5, 6details
#16ACCEPTED0.28 s4, 5, 6details
#170.07 s4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#210.65 s5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Code

#include <iostream>
#include <vector>

using namespace std;

int isA = 0, isB = 0, isC = 0, isD = 0, isE = 0,
        isF = 0, isG = 0, isH = 0, isI = 0, isJ = 0,
        isK = 0, isL = 0, isM = 0, isN = 0, isO = 0,
        isP = 0, isQ = 0, isR = 0, isS = 0, isT = 0,
        isU = 0, isV = 0, isW = 0, isX = 0, isY = 0, isZ = 0;

struct Dict {
    int A = 0, B = 0, C = 0, D = 0, E = 0,
        F = 0, G = 0, H = 0, I = 0, J = 0,
        K = 0, L = 0, M = 0, N = 0, O = 0,
        P = 0, Q = 0, R = 0, S = 0, T = 0,
        U = 0, V = 0, W = 0, X = 0, Y = 0, Z = 0;
    Dict operator=(Dict other) {
        A = other.A;
        B = other.B;
        C = other.C;
        D = other.D;
        E = other.E;
        F = other.F;
        G = other.G;
        H = other.H;
        I = other.I;
        J = other.J;
        K = other.K;
        L = other.L;
        M = other.M;
        N = other.N;
        O = other.O;
        P = other.P;
        Q = other.Q;
        R = other.R;
        S = other.S;
        T = other.T;
        U = other.U;
        V = other.V;
        W = other.W;
        X = other.X;
        Y = other.Y;
        Z = other.Z;
        return *this;
    }
    Dict operator+(const char type) {
        Dict res = *this;
        if (type == 'A') {
            res.A++;
            isA = 1;
        } else if (type == 'B') {
            res.B++;
            isB = 1;
        } else if (type == 'C') {
            res.C++;
            isC = 1;
        } else if (type == 'D') {
            res.D++;
            isD = 1;
        } else if (type == 'E') {
            res.E++;
            isE = 1;
        } else if (type == 'F') {
            res.F++;
            isF = 1;
        } else if (type == 'G') {
            res.G++;
            isG = 1;
        } else if (type == 'H') {
            res.H++;
            isH = 1;
        } else if (type == 'I') {
            res.I++;
            isI = 1;
        } else if (type == 'J') {
            res.J++;
            isJ = 1;
        } else if (type == 'K') {
            res.K++;
            isK = 1;
        } else if (type == 'L') {
            res.L++;
            isL = 1;
        } else if (type == 'M') {
            res.M++;
            isM = 1;
        } else if (type == 'N') {
            res.N++;
            isN = 1;
        } else if (type == 'O') {
            res.O++;
            isO = 1;
        } else if (type == 'P') {
            res.P++;
            isP = 1;
        } else if (type == 'Q') {
            res.Q++;
            isQ = 1;
        } else if (type == 'R') {
            res.R++;
            isR = 1;
        } else if (type == 'S') {
            res.S++;
            isS = 1;
        } else if (type == 'T') {
            res.T++;
            isT = 1;
        } else if (type == 'U') {
            res.U++;
            isU = 1;
        } else if (type == 'V') {
            res.V++;
            isV = 1;
        } else if (type == 'W') {
            res.W++;
            isW = 1;
        } else if (type == 'X') {
            res.X++;
            isX = 1;
        } else if (type == 'Y') {
            res.Y++;
            isY = 1;
        } else if (type == 'Z') {
            res.Z++;
            isZ = 1;
        }
        return res;
    }
    Dict operator+(const Dict& other) const {
        Dict res = *this;
        res.A = A + other.A;
        res.B = B + other.B;
        res.C = C + other.C;
        res.D = D + other.D;
        res.E = E + other.E;
        res.F = F + other.F;
        res.G = G + other.G;
        res.H = H + other.H;
        res.I = I + other.I;
        res.J = J + other.J;
        res.K = K + other.K;
        res.L = L + other.L;
        res.M = M + other.M;
        res.N = N + other.N;
        res.O = O + other.O;
        res.P = P + other.P;
        res.Q = Q + other.Q;
        res.R = R + other.R;
        res.S = S + other.S;
        res.T = T + other.T;
        res.U = U + other.U;
        res.V = V + other.V;
        res.W = W + other.W;
        res.X = X + other.X;
        res.Y = Y + other.Y;
        res.Z = Z + other.Z;
        return res;
    }
    Dict operator-(const Dict& other) const {
        Dict res = *this;
        res.A = A - other.A;
        res.B = B - other.B;
        res.C = C - other.C;
        res.D = D - other.D;
        res.E = E - other.E;
        res.F = F - other.F;
        res.G = G - other.G;
        res.H = H - other.H;
        res.I = I - other.I;
        res.J = J - other.J;
        res.K = K - other.K;
        res.L = L - other.L;
        res.M = M - other.M;
        res.N = N - other.N;
        res.O = O - other.O;
        res.P = P - other.P;
        res.Q = Q - other.Q;
        res.R = R - other.R;
        res.S = S - other.S;
        res.T = T - other.T;
        res.U = U - other.U;
        res.V = V - other.V;
        res.W = W - other.W;
        res.X = X - other.X;
        res.Y = Y - other.Y;
        res.Z = Z - other.Z;
        return res;
    }
    bool check() {
        if (A <= 0 && isA == 1) {
            return false;
        } else if (B <= 0 && isB == 1) {
            return false;
        } else if (C <= 0 && isC == 1) {
            return false;
        } else if (D <= 0 && isD == 1) {
            return false;
        } else if (E <= 0 && isE == 1) {
            return false;
        } else if (F <= 0 && isF == 1) {
            return false;
        } else if (G <= 0 && isG == 1) {
            return false;
        } else if (H <= 0 && isH == 1) {
            return false;
        } else if (I <= 0 && isI == 1) {
            return false;
        } else if (J <= 0 && isJ == 1) {
            return false;
        } else if (K <= 0 && isK == 1) {
            return false;
        } else if (L <= 0 && isL == 1) {
            return false;
        } else if (M <= 0 && isM == 1) {
            return false;
        } else if (N <= 0 && isN == 1) {
            return false;
        } else if (O <= 0 && isO == 1) {
            return false;
        } else if (P <= 0 && isP == 1) {
            return false;
        } else if (Q <= 0 && isQ == 1) {
            return false;
        } else if (R <= 0 && isR == 1) {
            return false;
        } else if (S <= 0 && isS == 1) {
            return false;
        } else if (T <= 0 && isT == 1) {
            return false;
        } else if (U <= 0 && isU == 1) {
            return false;
        } else if (V <= 0 && isV == 1) {
            return false;
        } else if (W <= 0 && isW == 1) {
            return false;
        } else if (X <= 0 && isX == 1) {
            return false;
        } else if (Y <= 0 && isY == 1) {
            return false;
        } else if (Z <= 0 && isZ == 1) {
            return false;
        } else {
            return true;
        }
    }
};

vector<vector<Dict>> cnt;

Dict getArea(int i1, int j1, int i2, int j2) {
    Dict area;
    if (i1 == 0 && j1 == 0) {
        area = cnt[i2][j2];
    } else if (i1 == 0) {
        area = cnt[i2][j2] - cnt[i2][j1 - 1];
    } else if (j1 == 0) {
        area = cnt[i2][j2] - cnt[i1 - 1][j2];
    } else {
        area = cnt[i2][j2] - cnt[i1 - 1][j2] - cnt[i2][j1 - 1] + cnt[i1 - 1][j1 - 1];
    }
    return area;
}

int main() {
    int n;
    cin >> n;
    vector<vector<char>> a(n, vector<char> (n));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            a[i][j] = s[j];
        }
    }
    cnt.resize(n, vector<Dict> (n));
    cnt[0][0] = cnt[0][0] + a[0][0];
    for (int i = 1; i < n; i++) {
        cnt[i][0] = cnt[i - 1][0] + a[i][0];
    }
    for (int i = 1; i < n; i++) {
        cnt[0][i] = cnt[0][i - 1] + a[0][i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
            cnt[i][j] = cnt[i][j] + a[i][j];
        }
    }
    int ans = 0;
    for (int i1 = 0; i1 < n; i1++) {
        for (int j1 = 0; j1 < n; j1++) {
            int preff = j1 - 1;
            for (int i2 = i1; i2 < n; i2++) {
                int l = preff;
                int r = n;
                while (r - l > 1) {
                    int m = (l + r) / 2;
                    if (getArea(i1, j1, i2, m).check()) {
                        r = m;
                    } else {
                        l = m;
                    }
                }
                //cout << r << ' ';
                preff = r - 2;
                if (!getArea(i1, j1, i2, r).check()) {
                    continue;
                }
                ans += (n - r);
            }
        }
    }
    cout << ans;
}

Test details

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
1470

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
3

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
3025

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
1
X

correct output
1

user output
1

Test 6

Group: 2, 3, 4, 5, 6

Verdict:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
36035

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
5148

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
44100

Test 9

Group: 2, 3, 4, 5, 6

Verdict:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
15

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1543881

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
641880

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1625625

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
1008

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
25122456

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
13114462

Test 16

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
25502500

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
16524

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
(empty)

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
8217915

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)