fork download
copy 
  1. #include <cassert>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <ctime>
  8. #include <algorithm>
  9. #include <bitset>
  10. #include <deque>
  11. #include <iostream>
  12. #include <iomanip>
  13. #include <limits>
  14. #include <list>
  15. #include <map>
  16. #include <queue>
  17. #include <set>
  18. #include <sstream>
  19. #include <stack>
  20. #include <utility>
  21. #include <vector>
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef long double ld;
  27. typedef pair <int, int> pii;
  28. typedef pair <ll, ll> pll;
  29. typedef vector <int> vi;
  30. typedef vector <string> vs;
  31.  
  32.  
  33. #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
  34. #define FORD(i, a, b) for (int i = (a); i >= (b); i--)
  35. #define REP(i, a) for (int i = 0; i < (a); i++)
  36. #define REPD(i, a) for (int i = ((a) - 1); i >= 0; i--)
  37. #define FIT(it, v) for (typeof((v).begin())it = (v).begin(); it != (v).end(); ++it)
  38. #define FITD(it, v) for (typeof((v).rbegin())it = (v).rbegin(); it != (v).rend(); ++it)
  39.  
  40. #define VAR(a, b) typeof(b) a(b)
  41. #define ALL(v) (v).begin(), (v).end()
  42. #define SET(a, x) memset((a), (x), sizeof(a))
  43. #define SIZE(a) ((int)(a).size())
  44.  
  45. #define EXIST(a, b) (find(ALL(a), (b)) != (a).end())
  46. #define SORT(x) sort(ALL(x))
  47. #define GSORT(x) sort(ALL(x), greater<typeof(*((x).begin()))>())
  48. #define UNIQUE(v) SORT(v); (v).resize(unique(ALL(v)) - (v).begin())
  49. #define ENUM(v) FIT(it, (v)) cout << *it << " "; cout << endl
  50.  
  51. #define PF push_front
  52. #define PB push_back
  53. #define MP make_pair
  54. #define F first
  55. #define S second
  56.  
  57. // bit operater
  58. int BIT(ll x,int i) { return(x&(1<<i));}
  59. ll ONBIT(int i,ll x){ return(x|(1<<i));}
  60. ll OFFBIT(int i,ll x){return (x& ~(1<<i));}
  61. ll FLIPBIT(int i,ll x){return (x^(1<<i));}
  62.  
  63. const char IN[] = "_.in";
  64. const char OUT[] = "_.out";
  65. const int maxn=310;
  66. const int offset=40000;
  67. int n,f;
  68. int a[100];
  69. int visited[51][80100];
  70. int sig[51][80100];
  71. bool ok[100][3];
  72. bool can;
  73. void dp(int i,int val)
  74. {
  75. 	if (visited[i][val]!=-1) 
  76. 	{
  77. 		if (visited[i][val]==1)
  78. 		{
  79. 			can=true;
  80. 			int tg=f+offset;
  81. 			int id=n;
  82. 			while (tg!=offset || id!=0)
  83. 			{
  84. 				if (sig[id][tg]==1) 
  85. 				{
  86. 					ok[id][1]=true;
  87. 					tg=tg-a[id];
  88. 					id--;
  89. 				}
  90. 				else
  91. 				if (sig[id][tg]==0) 
  92. 				{
  93. 					ok[id][0]=true;
  94. 					tg=tg+a[id];
  95. 					id--;
  96. 				}
  97. 			}			
  98. 		}
  99. 		return;		
  100. 	}	
  101.  
  102. 	if (i==n+1)
  103. 	{
  104. 		if (val==f+offset)
  105. 		{
  106. 			int tg=f+offset;
  107. 			int id=n;
  108. 			while (tg!=offset || id!=0)
  109. 			{
  110. 				if (sig[id][tg]==1) 
  111. 				{
  112. 					ok[id][1]=true;
  113. 					tg=tg-a[id];
  114. 					id--;
  115. 				}				
  116. 				else
  117. 				if (sig[id][tg]==0) 
  118. 				{
  119. 					ok[id][0]=true;
  120. 					tg=tg+a[id];
  121. 					id--;
  122. 				}
  123. 			}
  124. 		    can=true;
  125. 		    visited[i][val]=true;		    
  126. 		}	
  127. 		else
  128. 		{
  129. 			visited[i][val]=false;
  130. 		}
  131. 		return;		
  132. 	}
  133.  
  134.  
  135. 	sig[i][val+a[i]]=1; // +
  136. 	dp(i+1,val+a[i]);
  137. 	if (visited[i+1][val+a[i]]==true)
  138. 	{
  139. 		visited[i][val]=true;		
  140. 	}
  141. 	sig[i][val-a[i]]=0; // -
  142. 	dp(i+1,val-a[i]);
  143. 	if (visited[i+1][val-a[i]])
  144. 	{
  145. 		visited[i][val]=true;		
  146. 	}	
  147. 	if (visited[i][val]==-1) visited[i][val]=0;    
  148. 	return;
  149. }
  150. int main() {
  151.   //freopen(IN, "r", stdin);
  152.   //freopen(OUT, "w", stdout);  
  153.   while (cin>>n>>f)
  154.   {
  155.   	if (n==0 && f==0) break;
  156.   	FOR(i,1,n) cin>>a[i];
  157.   	SET(sig,-1);
  158.   	SET(visited,-1);
  159.   	SET(ok,false);
  160.   	can=false;
  161.   	dp(1,offset);  	
  162.   	if (can==false) puts("*");
  163.   	else
  164.   	{
  165.   		FOR(i,1,n)
  166.   		if (ok[i][1] && ok[i][0]) printf("?");
  167.   		else
  168.   		if (ok[i][0]) printf("-");
  169.   		else
  170.   		if (ok[i][1]) printf("+");
  171.   		puts("");
  172.   	}
  173.   }
  174.   return 0;
  175. }
Success #stdin #stdout 0.03s 35264KB
comments (?)
stdin
copy 
10 14
3 2 1 1 2 3 2 3 3 2
0 0
stdout
copy 
++???+?+??
https://ideone.com/6Y3S2p
language:
C++ (gcc 8.3)
created:
9 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!