fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<long long, int> pii;
  5. typedef vector<pii> vii;
  6. const ll INF=1LL<<63-1;
  7.  
  8. string s[2];
  9. int n;
  10. unordered_map<string,int> c[2],nc[2];
  11.  
  12. string rev(string ss,int i,int j){
  13. 	while(i<j) swap(ss[i++],ss[j--]);
  14. 	return ss;
  15. }
  16.  
  17. bool insert(int from,const string prev,int pi,int pj){
  18. 	for(int i=0;i<=pi;i++){
  19. 		for(int j=pj;j<n;j++){
  20. 			if(i!=pi || j!=pj){
  21. 				string k=rev(prev,i,j);
  22. 				//cout<<prev<<" "<<k<<i<<j<<endl;
  23. 				if(c[from^1].count(k)){
  24. 					return true;
  25. 				}else
  26. 				nc[from][k]=i*16+j;
  27. 			}
  28. 		}
  29. 	}
  30. 	for(int i=pj+1;i<n;i++){
  31. 		for(int j=i+1;j<n;j++){
  32. 				string k=rev(prev,i,j);
  33. 				//cout<<prev<<" "<<k<<i<<j<<endl;
  34. 			if(c[from^1].count(k)){
  35. 				return true;
  36. 			}else
  37. 			nc[from][k]=i*16+j;
  38. 		}
  39. 	}
  40. 	return false;
  41. }
  42.  
  43. int bfs(){
  44. 	if(s[0]==s[1]) return 0;
  45. 	c[0].clear();c[1].clear();
  46. 	c[0][s[0]]=0;
  47. 	c[1][s[1]]=0;
  48. 	for(int d=1;d<n;d++){
  49. 		nc[d%2].clear();
  50. 		for(auto st:c[d%2]){
  51. 			if(insert(d%2,st.first,st.second/16,st.second%16)){
  52. 				return d;
  53. 			}
  54. 		}
  55. 		c[d%2]=nc[d%2];
  56. 	}
  57. 	return n;
  58. }
  59.  
  60. int main() {
  61. 	cin>>s[0]>>s[1];n=s[0].size();
  62. 	int d=bfs();cin>>s[0];
  63. 	cout<<d+bfs();
  64. 	return 0;
  65. }
Success #stdin #stdout 0.85s 88128KB
comments (?)
stdin
copy 
abcdefghijklm ehldmbgjifkac abcdefghijklm
stdout
copy 
18
https://ideone.com/kE2v4c
enter your note really horrible string problem
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!