fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int 
  4. #define pi pair<int ,int >
  5. #define pl pair<ll ,ll >
  6. #define pb push_back
  7. #define vl vector <long long int >
  8. #define vi vector <int >
  9. #define vp vector <pi>
  10. #define mod 1000000007
  11. #define eps 1e-9
  12. #define fi first
  13. #define se second
  14. #define all(x) x.begin(), x.end()
  15. #define _ <<" "<<
  16. #define forn(x,	n) for(int x = 0; x < n ;++ x) 
  17. #define forn1n(x,n) for(int x = 1; x <= n ;++ x)
  18. #define forn1(x,n) for(int x = 1; x < n ;++ x)
  19. #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  20. #pragma GCC optimize ("Ofast")
  21. void scan(){}
  22. template<typename F, typename... R> void scan(F &f,R&... r){cin>>f;scan(r...);}
  23. int di_; string dnms_, co_ = ",";
  24. void debug_(){cout<<endl;}
  25. template<typename F, typename... R> void debug_(F &f, R&... r){while(dnms_[di_] != ',')cout<<dnms_[di_++];di_++;cout<<": "<<f<<",";debug_(r...);}
  26. #define debug(...) dnms_=#__VA_ARGS__+co_,di_=0,debug_(__VA_ARGS__)
  27.  
  28. template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &a){
  29.     return out<<"("<<a.first<<","<<a.second<<")";}
  30. template<class A> ostream& operator<<(ostream& out, const vector<A> &a){
  31. 	out<<"";for(auto it=a.begin();it!=a.end();it++){if(it!=a.begin())out<<" ";out<<*it;}out<<"";
  32. 	return out;}
  33. template<class A, class B> istream& operator>>(istream& in, pair<A,B> &a){in>>a.first>>a.second;return in;}
  34. template<class A> istream& operator>>(istream& in, vector<A> &a){for(A &i:a)in>>i;return in;}
  35.  
  36. struct HASH{
  37.   size_t operator()(const pair<int,int>&x)const{
  38.     return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  39.   }
  40. };
  41.  
  42. string s;
  43. vector<string>v;
  44. const int N = 11;
  45. unordered_map<pair<int,int>,vector<int> ,HASH>dp;
  46. bool isop(char ch)
  47. {
  48. 	return ch == '&'||ch == '|' || ch == '^'; // Check if it is an operator
  49. }
  50.  
  51. int ansop(int x,int y,char op)
  52. {
  53. 	// return the resultant after operation
  54.  
  55. 	if(op=='|')
  56. 		return int(x)|int(y);
  57. 	else if(op=='&')
  58. 		return int(x)&int(y);
  59. 	else
  60. 		return int(x)^int(y);
  61. }
  62. vector<int> solve(int i, int j)
  63. {
  64. 	if(i==j)
  65. 		return {stoi(v[i])}; // If we've only one element group then just return it
  66. 	if(!dp[{i,j}].empty())
  67. 		return dp[{i,j}];    // memoization
  68. 	vector<int> pa;          // possible answers
  69. 	for(int k=i+1;k<j;k+=2)
  70. 	{
  71.  
  72. 		assert(isop(v[k][0]));            // assure that we're splitting on a operator
  73. 		vector<int> left = solve(i,k-1);  // possible reluts of left group
  74. 		vector<int> right = solve(k+1,j); // possible results of right grp
  75.  
  76. 		for(auto& l:left)
  77. 			for(auto& r:right)
  78. 			{
  79. 				pa.pb(ansop(l,r,v[k][0])); // try every possible combination
  80. 			}
  81. 		sort(all(pa));
  82. 		pa.erase(unique(all(pa)),pa.end()); // remove repeating elements
  83. 	}
  84. 	return pa;
  85. }
  86. int main(){
  87. 	IOS
  88.  
  89. 	int t;
  90. 	cin>>t;
  91. 	while(t--)
  92. 	{
  93. 		cin>>s;
  94. 		v.clear();
  95. 		int lindex=0;
  96. 		forn1(i,s.size())
  97. 		{
  98. 			if(isop(s[i]))
  99. 				{
  100. 					v.push_back(s.substr(lindex,i-lindex));
  101. 					v.push_back(s.substr(i,1));
  102. 					lindex=i+1;
  103. 				}
  104. 		}
  105. 		v.push_back(s.substr(lindex,s.size()-lindex));
  106. 		auto ans = solve(0,v.size()-1);
  107. 		cout<<ans.back()<<endl;
  108. 	}
  109. 	return 0;	
  110. }
Runtime error #stdin #stdout #stderr 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoi
https://ideone.com/Fety9e
language:
C++14 (gcc 8.3)
created:
4 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!