fork(8) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ivector = vector<int>;
  4. using imatrix = vector<ivector>;
  5.  
  6. const auto first = 'a', last = 'z';
  7. const int M = last-first, U = M+1;
  8.  
  9. auto nextInt(istream& cin) { int    num; cin >> num; return num; }
  10. auto nextStr(istream& cin) { string str; cin >> str; return str; }
  11. auto randomStr(mt19937& random, int n) {
  12. 	uniform_int_distribution<int> uniform_letter(0,M);
  13. 	string s;
  14. 	while (n--)
  15. 		s += char(first+uniform_letter(random));
  16. 	return s; }
  17.  
  18. struct problem {
  19. 	const int    n;
  20. 	const string s;
  21. 	problem(istream& stream): n(nextInt(stream)), s(nextStr(stream)) {} 
  22. 	problem(mt19937& random, int size) : n(size), s(randomStr(random,n)) {} 
  23. 	ostream& write(ostream& stream) const {
  24. 		return stream << n << endl << s << endl; }
  25. 	friend ostream& operator<<(ostream& stream, const problem& prob) {
  26. 		return prob.write(stream); } };
  27.  
  28. struct solution: problem {
  29. 	int m, min_length = numeric_limits<int>::max();
  30. 	imatrix prefix;
  31. 	auto is_palindrome_without(int l, int r) {
  32. 		int odd = 0;
  33. 		for (int i = 0; i < U; ++i)
  34. 			odd += (prefix[l][i]+(prefix[n][i]-prefix[r][i]))&1;
  35. 		return odd < 2; } 
  36. 	solution(const problem& prob) : 
  37. 		problem(prob), m(n+1), prefix(m,ivector(U)) {
  38. 		for (int l = 0, r = 1; l < n; l = r++)
  39. 			prefix[r] = prefix[l], ++prefix[r][s[l]-first]; 
  40. 		if (is_palindrome_without(0,0))
  41. 			min_length = 0; } };
  42.  
  43. struct brute_force: solution {
  44. 	brute_force(const problem& prob): solution(prob) {
  45. 		if (min_length > 0)
  46. 			for (min_length = 1; min_length < n; ++min_length)
  47. 				for (int r = min_length; r <= n; ++r)
  48. 					if (is_palindrome_without(r-min_length,r))
  49. 						return; } };
  50.  
  51. struct map_based: solution {
  52. 	ivector g;
  53. 	unordered_map<int,ivector> h;
  54. 	auto update(int l, const ivector &f) {
  55. 		const auto b = f.begin(), e = f.end(), c = upper_bound(b,e,l);
  56. 		if (c != e)
  57. 			min_length = min(min_length,*c-l); }
  58. 	auto check(int l, int key) {
  59. 		const auto it = h.find(key);
  60. 		if (it != h.end()) 
  61. 			update(l,it->second); }
  62. 	map_based(const problem& prob): solution(prob), g(m) {
  63. 		if (min_length == 0)
  64. 			return;
  65. 		for (int i = 0; i < m; ++i)
  66. 			for (int b = 1, j = 0; j < U; ++j, b <<= 1)
  67. 				if (prefix[i][j]&1)
  68. 					g[i] |= b;
  69. 		for (int x = g[n], r = 1; r <= n; ++r)
  70. 			h[g[r]^x].push_back(r);
  71. 		for (int l = 0; l < n; ++l) {
  72. 			const int x = g[l];
  73. 			check(l,x);
  74. 			for (int b = 1, j = 0; j < U; ++j, b <<= 1)
  75. 				check(l,x^b); } } };
  76.  
  77. auto test_main() {
  78. 	random_device device;
  79. 	mt19937 random(device());
  80. 	int T, size;
  81. 	cin >> T >> size;
  82. 	for (int test = 1; test <= T; ++test) {
  83. 		const problem prob(random,size);
  84. 		const auto b = brute_force(prob).min_length;
  85. 		const auto m =   map_based(prob).min_length;
  86. 		if (m != b) {
  87. 			cout << "In test " << test << endl;
  88. 			cout << prob;
  89. 			cout << "computed = " << m << endl;
  90. 			cout << "expected = " << b << endl;
  91. 			return 0; } }
  92. 	cout << "passed";
  93. 	return 0; }
  94.  
  95. auto submission_main() {
  96. 	cin.tie(nullptr)->sync_with_stdio(false);
  97. 	for (int t = nextInt(cin); t--; )
  98. 		cout << map_based(problem(cin)).min_length << endl;
  99. 	return 0; }
  100.  
  101. int main() {
  102. 	return test_main(); }
  103.  
Success #stdin #stdout 6.69s 5436KB
comments (?)
stdin
copy 
200000 25
stdout
copy 
passed
https://ideone.com/GJfmuR
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!