QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31263#2106. DrukQingyu100 ✓61ms11124kbC++232.4kb2022-05-05 23:50:552022-05-05 23:50:58

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-05 23:50:58]
  • 评测
  • 测评结果:100
  • 用时:61ms
  • 内存:11124kb
  • [2022-05-05 23:50:55]
  • 提交

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