Task: | Niitty |
Sender: | Mariia |
Submission time: | 2024-11-07 19:45:09 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 33 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 4 |
#2 | ACCEPTED | 6 |
#3 | ACCEPTED | 10 |
#4 | ACCEPTED | 13 |
#5 | TIME LIMIT EXCEEDED | 0 |
#6 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#2 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#3 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#4 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#5 | ACCEPTED | 0.00 s | 1, 2, 3, 4, 5, 6 | details |
#6 | ACCEPTED | 0.01 s | 2, 3, 4, 5, 6 | details |
#7 | ACCEPTED | 0.01 s | 2, 3, 4, 5, 6 | details |
#8 | ACCEPTED | 0.01 s | 2, 3, 4, 5, 6 | details |
#9 | ACCEPTED | 0.01 s | 2, 3, 4, 5, 6 | details |
#10 | ACCEPTED | 0.03 s | 3, 4, 5, 6 | details |
#11 | ACCEPTED | 0.03 s | 3, 4, 5, 6 | details |
#12 | ACCEPTED | 0.04 s | 3, 4, 5, 6 | details |
#13 | ACCEPTED | 0.03 s | 3, 4, 5, 6 | details |
#14 | ACCEPTED | 0.27 s | 4, 5, 6 | details |
#15 | ACCEPTED | 0.24 s | 4, 5, 6 | details |
#16 | ACCEPTED | 0.27 s | 4, 5, 6 | details |
#17 | ACCEPTED | 0.23 s | 4, 5, 6 | details |
#18 | TIME LIMIT EXCEEDED | -- | 5, 6 | details |
#19 | TIME LIMIT EXCEEDED | -- | 5, 6 | details |
#20 | TIME LIMIT EXCEEDED | -- | 5, 6 | details |
#21 | TIME LIMIT EXCEEDED | -- | 5, 6 | details |
#22 | TIME LIMIT EXCEEDED | -- | 6 | details |
#23 | TIME LIMIT EXCEEDED | -- | 6 | details |
#24 | TIME LIMIT EXCEEDED | -- | 6 | details |
#25 | TIME LIMIT EXCEEDED | -- | 6 | details |
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++) { for (int i2 = i1; i2 < n; i2++) { int l = j1 - 1; 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 << ' '; 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: ACCEPTED
input |
---|
10 TNCTNPNTPC NPPNTNTPTP NTNTTCNTCT NPCPNPPNTT ... |
correct output |
---|
2035 |
user output |
---|
2035 |
Test 2
Group: 1, 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
10 NFWQLWNWYS DZOQJVXFPJ CNHXPXMCQD QRTBVNLTQC ... |
correct output |
---|
9 |
user output |
---|
9 |
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: ACCEPTED
input |
---|
20 BBCBUBOUOBBCUUBBCOUO BOUCOOCUBCOOOCOBOCUO UCCUUUOBCOCBCBUBUCOO BUOBUCUCUOOBCOOUBUOO ... |
correct output |
---|
38724 |
user output |
---|
38724 |
Test 7
Group: 2, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
20 CBGLSHGZHYZDWBNDBJUG SMUXOJQYPXZDTMJUIWOJ XIDSTNBGHKRKOVUVMINB MTQGCFRUHQKALXRNCQGS ... |
correct output |
---|
8334 |
user output |
---|
8334 |
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: ACCEPTED
input |
---|
20 AAAAAAAAXAAAAAAAAAAA AAAWAAAAAAAAAAAAAOAA AAAAAAAAAAAAAAAAAPAA AAAAAAAAKAAAAAAAAAAZ ... |
correct output |
---|
18 |
user output |
---|
18 |
Test 10
Group: 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
50 GRGREEEGREGXRXXEGXXREXGRRRGRRR... |
correct output |
---|
1584665 |
user output |
---|
1584665 |
Test 11
Group: 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
50 AITIISJUHCCRZNKSDCNQKYSQRINFWJ... |
correct output |
---|
1077746 |
user output |
---|
1077746 |
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: ACCEPTED
input |
---|
50 FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF... |
correct output |
---|
1680 |
user output |
---|
1680 |
Test 14
Group: 4, 5, 6
Verdict: ACCEPTED
input |
---|
100 NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM... |
correct output |
---|
25325366 |
user output |
---|
25325366 |
Test 15
Group: 4, 5, 6
Verdict: ACCEPTED
input |
---|
100 LIMQQIHASECROEVILNVULGWZJPPKOG... |
correct output |
---|
22342463 |
user output |
---|
22342463 |
Test 16
Group: 4, 5, 6
Verdict: ACCEPTED
input |
---|
100 TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT... |
correct output |
---|
25502500 |
user output |
---|
25502500 |
Test 17
Group: 4, 5, 6
Verdict: ACCEPTED
input |
---|
100 QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ... |
correct output |
---|
25650 |
user output |
---|
25650 |
Test 18
Group: 5, 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 NAANANMMKNKKAKMKMAKNKMNKMMNNAA... |
correct output |
---|
403292767 |
user output |
---|
(empty) |
Test 19
Group: 5, 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 OMYWATTLURKQPTKEFMGGYAOONXWVSC... |
correct output |
---|
388111321 |
user output |
---|
(empty) |
Test 20
Group: 5, 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC... |
correct output |
---|
404010000 |
user output |
---|
(empty) |
Test 21
Group: 5, 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
200 LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL... |
correct output |
---|
14159445 |
user output |
---|
(empty) |
Test 22
Group: 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW... |
correct output |
---|
15683003812 |
user output |
---|
(empty) |
Test 23
Group: 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE... |
correct output |
---|
15575906951 |
user output |
---|
(empty) |
Test 24
Group: 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 IIIIIIIIIIIIIIIIIIIIIIIIIIIIII... |
correct output |
---|
15687562500 |
user output |
---|
(empty) |
Test 25
Group: 6
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW... |
correct output |
---|
3058970930 |
user output |
---|
(empty) |