fork download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2.  
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. #define ll long long
  8. #define endl "\n"
  9. #define rep(i,n) for(int i=0;i<n;i++)
  10.  
  11.  
  12. int solve(string s,string t)
  13. {
  14. 	queue<string>q;
  15. 	q.push(s);
  16. 	unordered_map<string,int>level;
  17. 	level[s]=0;
  18. 	int l = s.size();
  19. 	while(!q.empty())
  20. 	{
  21. 		string cur =  q.front();
  22. 		q.pop();
  23. 		for(int i=0;i<l;i++)
  24. 		{
  25. 			string first ="";
  26. 			if(i!=0) first = cur.substr(0,i);
  27. 			string tmp = cur.substr(i,1);
  28. 			for(int j=i+1;j<l;j++)
  29. 			{
  30. 				tmp+=cur[j];
  31. 				reverse(tmp.begin(),tmp.end());
  32. 				string newStr = first+tmp;
  33. 				//cout<<newStr<<" ||\n";
  34. 				if(newStr.size()<l)
  35. 				{
  36. 					newStr+=cur.substr(j+1,10-j);
  37. 				}
  38. 				if(level.find(newStr)==level.end())
  39. 				{
  40. 					level[newStr] = level[cur]+1;
  41. 					q.push(newStr);
  42. 				}
  43. 				if(newStr==t)return level[cur]+1;
  44. 				//cout<<newStr<<endl;
  45. 				reverse(tmp.begin(),tmp.end());
  46. 			}
  47. 		}
  48. 	}
  49. 	return -1;
  50. }
  51.  
  52.  
  53. int main()
  54. {
  55. 	#ifndef ONLINE_JUDGE
  56. 		freopen("input.txt","r",stdin);
  57. 		freopen("out.txt","w",stdout);
  58. 	#endif
  59. 	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  60. 	string src,tar;
  61. 	while(cin>>tar>>src)
  62. 	{
  63. 		if(src=="*" && tar=="*")break;
  64. 		if(src==tar)cout<<"0\n";
  65. 		for(int i=0;i<10;i++)
  66. 		{
  67. 			if(src[i]!=tar[i])
  68. 			{
  69. 				string s="",t="";
  70. 				for(int j=i;j<10;j++)s+=src[j],t+=tar[j];
  71. 				cout<<solve(s,t)<<"\n";
  72. 				break;
  73. 			}
  74. 		}
  75. 	}
  76. 	return 0;
  77. }
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Mf1Igo
problem INVESORT, based on SPOJ submission 29774423 (CPP14), 2022-07-06 09:00:44
language:
C++14 (gcc 8.3)
created:
2 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!