QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31263 | #2106. Druk | Qingyu | 100 ✓ | 61ms | 11124kb | C++23 | 2.4kb | 2022-05-05 23:50:55 | 2022-05-05 23:50:58 |
Judging History
answer
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> a(n, std::vector<int>(m));
std::vector<int> cnt(26);
int sigma = 0;
for (int i = 0; i < n; ++i) {
std::string s;
std::cin >> s;
for (int j = 0; j < m; ++j) {
a[i][j] = s[j] - 'a';
if (!cnt[s[j] - 'a']) {
++sigma;
}
++cnt[s[j] - 'a'];
}
}
auto solve = [&](int d, auto &pattern) -> bool {
std::vector<std::vector<int>> covered(n, std::vector<int>(m));
char c1 = pattern[0], c2 = c1;
int kp = -1;
for (int i = 0; i < d; ++i)
if (pattern[i] != c1) {
c2 = pattern[i];
kp = i;
break;
}
if (kp == -1)
return false;
auto try_match_row = [&](int i, int j) {
if (j + d > m)
return false;
for (int k = 0; k < d; ++k)
if (a[i][j + k] != pattern[k] || covered[i][j + k])
return false;
for (int k = 0; k < d; ++k)
covered[i][j + k] = true;
return true;
};
auto try_match_column = [&](int i, int j) {
if (i + d > n)
return false;
for (int k = 0; k < d; ++k)
if (a[i + k][j] != pattern[k] || covered[i + k][j])
return false;
for (int k = 0; k < d; ++k)
covered[i + k][j] = true;
return true;
};
// O(nm)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
if (!covered[i][j] && a[i][j] == c1 && !try_match_row(i, j)) {
if (!try_match_column(i, j)) {
return false;
}
}
for (int j = 0; j < m; ++j)
if (!covered[i][j] && a[i][j] != c1) {
if (!try_match_column(i, j)) {
return false;
}
}
}
return true;
};
std::vector<int> ret;
for (int d = 1; d <= std::max(n, m); ++d)
if (n % d == 0 || m % d == 0) {
if (sigma == 1) {
ret.push_back(d);
continue;
}
int total = n * m / d;
for (int i = 0; i < 26; ++i)
if (cnt[i] % total != 0)
continue;
std::vector<int> bs(d);
if (d <= m) {
for (int i = 0; i < d; ++i)
bs[i] = a[0][i];
if (solve(d, bs)) {
ret.push_back(d);
continue;
}
}
if (d <= n) {
for (int i = 0; i < d; ++i)
bs[i] = a[i][0];
if (solve(d, bs)) {
ret.push_back(d);
continue;
}
}
}
std::cout << ret.size() << '\n';
for (int x : ret)
std::cout << x << " ";
std::cout << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 3ms
memory: 3588kb
input:
1 1000 ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
12 2 4 8 10 20 40 50 100 200 250 500 1000
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
1 720 yddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyydyddyyd...
output:
1 720
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
1 810 prprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprpprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprpprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprprpprprprprprprprprprprprprprprprprprprprprprprprprprp...
output:
4 81 162 405 810
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
1 888 jwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnroxjwrevwivsdljtckxfqzeymqgbsmnsjxtfnr...
output:
8 37 74 111 148 222 296 444 888
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
1 864 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
24 1 2 3 4 6 8 9 12 16 18 24 27 32 36 48 54 72 96 108 144 216 288 432 864
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
1 1000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
16 1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000
result:
ok 2 lines
Subtask #2:
score: 25
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 25
Accepted
time: 1ms
memory: 3612kb
input:
3 1000 ababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaababbaabbaaba...
output:
9 10 20 40 50 100 200 250 500 1000
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 2ms
memory: 3676kb
input:
3 900 ahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhzahazhz...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
2 1000 abaabaaaaaaaaabaaabaabaabaaaaaaababaaabaaaabaaaaaaaabaaababaababaaaaabaaabaaabaabaababaabaaaabaaaababaabaaaaaaaaaababaababaaabaaababaaaabaabaabaabababaaabaababaabaaabaaababaababaababaababaaaaaaaaaaaaaabababaaaaaaabaaaababaabababaaaabaaabaabaaaabaabaababaabaaaaaaaabaaaaaaaaaaaaaaaaaaababaaabaa...
output:
1 2
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 1000 klklklkklkklklklklklklklklklklklklkkkklklklkklklklkkkklkklklkklkklkklkkklkklkkklklklklklklklklkklklklklkklklklklklklklklklkklklklklkklklkkklklkkklklklklklklklklkklkklklklklklklklklklkkklklklkkklklklkklklklkkkklkkkkklklklklklklklkklklklkklklkklklklklklkkkkkklklklkkklkkklklklklklklklklklklklklk...
output:
1 2
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
3 1000 ooopopopopoopooopopooopopopoopopopooooooopopopoooopoopopopoopopooopopooopoooopopopopopopopopoopopopoopooopopopopopopopopopopopopopopopopopopoopopooopoopopopopopopopopopopopopopopopoooooopoopopoopopoooopopopopoopopopopopopopopoopoooopoopopoooopopooopopopopopooopopoopopopopopoopopoopopopopopopo...
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 3ms
memory: 3604kb
input:
3 1000 ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
12 2 4 8 10 20 40 50 100 200 250 500 1000
result:
ok 2 lines
Subtask #3:
score: 20
Accepted
Test #13:
score: 20
Accepted
time: 1ms
memory: 3720kb
input:
20 20 eeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeeeeeeeee eegeeeeeegeeeeeeeeee eeeeeeeeeeegeeeeeeee eeeeeeeeeeeeeeeeeeee eeeeeeeegeeeeeeeeege eeeeeeeeeeeeeegeeeee eeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeeeeeeeee eeegeeegeeeeeeeeeeee eeeeeeeeeeeeeeeeeeee eeeeeeeeeeeeeegeeeee eeeeggeeeeeeeeeeeeee eeeeeeeeeeeeeeegeege ...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 4ms
memory: 3564kb
input:
3 8 ababaaba babaabab abaababa
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
18 15 aabaaaabaabaaba aabaaaabaaabaaa aabbbaaaaaaaaab aaabaaaabaaabba aaababbbabbbaaa baaabaaaaaaaaab aaaaaaaabaaabba abbbabbbabbbaaa baaabaaaaaaaaab aaaaaaaabaaabba abbbabbbabbbaaa baabbaabaaabaab aaabaaabbaaabba aaaaaaabaaaaaaa baaabaaaabbbaab abbbaaaabaabbba aaababbbaabaaba baabbaabaabaabb
output:
1 3
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
14 15 abababaabababaa abababaaaaaaaab aaaaaaabbbbbbba bbbbbbbaaaaaaab aaaaaaabbbbbbba bbbbbbbaaaaaaab aaaaaaabbbbbbba bbbbbbbaaaaaaaa aaaaaaaabababab abababaabababaa abababaabababab abababaabababaa abababaabababab abababaabababaa
output:
1 7
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 3ms
memory: 3668kb
input:
4 9 aabaaabaa babababab aabaaabaa abaabaaba
output:
1 3
result:
ok 2 lines
Subtask #4:
score: 45
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #18:
score: 45
Accepted
time: 8ms
memory: 5220kb
input:
512 729 pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
16 1 2 3 4 8 9 16 27 32 64 81 128 243 256 512 729
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 1ms
memory: 6488kb
input:
800 918 kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...
output:
32 1 2 3 4 5 6 8 9 10 16 17 18 20 25 27 32 34 40 50 51 54 80 100 102 153 160 200 306 400 459 800 918
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 1ms
memory: 6784kb
input:
924 871 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
27 1 2 3 4 6 7 11 12 13 14 21 22 28 33 42 44 66 67 77 84 132 154 231 308 462 871 924
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 3ms
memory: 3544kb
input:
62 48 abaabaabaabaaabaabaabaabaaabaabaabaabaaaaaaaaaaa abaabaabaabababaabaabaababaaaaaaaaaaaabbbbbbbbbb abaabaabaabaaabaabaabaabaabbbbbbbbbbbbaaaaaaaaaa abaabaabaabaaabaabaabaabaaaaaaaaaaaaaaaaaaaaaaaa abaabaabaabababaabaabaababaaaaaaaaaaaabbbbbbbbbb aaaaaaaaaaaaaabaabaabaabaabbbbbbbbbbbbaaaaaaaaaa ...
output:
3 3 6 12
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 19ms
memory: 11124kb
input:
1000 1000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0
result:
ok single line: '0'
Test #23:
score: 0
Accepted
time: 34ms
memory: 7428kb
input:
600 900 abacabacabacaaaabacabacabacaaaaabacabacabacabacabacabacaaaaaaabacabacabacabacabacabacaaaaaabacabacabacabacabacabacaaaaaaabacabacabacaaabacabacabacaaaaabacabacabacabacabacabacaaaaaaaabacabacabacaaaabacabacabacaaabacabacabacaaabacabacabacaaaaaabacabacabacabacabacabacaaaaaaabacabacabacabacabaca...
output:
2 4 12
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 36ms
memory: 11120kb
input:
1000 1000 ababababaaaababababaaababababaaaaaaaaaaaaababababaaaababababaababababaababababaaaababababababababaaaaababababababababaaaababababaaababababaaababababaaaababababaaababababababababaaaaababababababababaaaababababaababababaaaaaababababaaababababaababababababababaaaababababababababaaaaaababababa...
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 61ms
memory: 10872kb
input:
960 1000 aababababababababababababaaaaaaaaaaaaaaaaaaaaaaaaaababababababababababababababababababababababababaaaaaababababababababababababaaaaaaaaaaaaaaaaaaaaaaaaaaababababababababababababaaaaaaaaaaaaaaaaaaaaaaaababababababababababababababababababababababababaaababababababababababababaaabababababababa...
output:
6 2 4 6 8 12 24
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 39ms
memory: 10920kb
input:
984 984 ababababababababababababaaaababababababababababababaaaaaaaaaaaaababababababababababababaababababababababababababaaaaaaaaaaaaaaaaababababababababababababababababababababababababaaaaaaaaaaaaaababababababababababababababababababababababababaaaaaaaaaaaaaaaaabababababababababababababababababababa...
output:
2 2 6
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 34ms
memory: 7676kb
input:
700 800 aabaaabaabababaabaaabaabaaaabaaaaaaaaaaaaaaaabaaabaaaaaaaaaabaaabababababaaaaaaaabaaabaaabababaabaaabaabababaaaaaaaaaaaaaaabaaababababababaaabababababaaaaaaaaaaabaaababababababaaabaaaaaaaaaaaaaaaaaaaaaabaaababababababaaabababababaaaaaaaaaaaaabaaabaaaaaaababaaabababababaaaaaaaaaaaabaaabaababa...
output:
0
result:
ok single line: '0'
Test #28:
score: 0
Accepted
time: 32ms
memory: 11116kb
input:
1000 1000 abbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaabbaaaaaab...
output:
1 4
result:
ok 2 lines
Extra Test:
score: 0
Extra Test Passed