Source code for submission s962

fq.cpp

  1. #include<iostream>
  2.  
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<ctype.h>
  6. #include<math.h>
  7.  
  8. #include<vector>
  9. #include<map>
  10.  
  11. using namespace std;
  12.  
  13. #define FOR(i,a,b) for(int i=a; i<=b; i++)
  14.  
  15. #define PII pair<int, int>
  16. #define MP make_pair
  17. #define PB push_back
  18.  
  19. #define SIZE(s) (int)(s).int()
  20.  
  21. #define ll long long
  22.  
  23. #define INF -1
  24. #define MIL 1000000
  25. #define MIL2 10000000
  26.  
  27. char s[1001];
  28.  
  29. #define MAX 1005
  30. #define MAX2 505
  31.  
  32. map<ll, int> M;
  33.  
  34. ll toH(int a, int b, int c)
  35. {
  36. 	return ((ll) c) + (ll)b*1000L + (ll)a * 1000000L;
  37. }
  38.  
  39. int poc(int p, int o, int z)
  40. {
  41. 	ll index = toH(p,o,z);
  42.  
  43. 	if (M.find(index) != M.end())
  44. 		return M[index];
  45.  
  46. 	if(z>o)
  47. 	{
  48. 		M[index] = INF;
  49. 		return INF;
  50. 	}
  51.  
  52. 	if(s[p] == '(')
  53. 		o++;
  54. 	if(s[p] == ')')
  55. 		z++;
  56.  
  57. 	if( p == (int) strlen(s) -1)
  58. 	{
  59. 		if(s[p] == '.')
  60. 			z++;
  61.  
  62. 		if(z != o || s[p] == '(')
  63. 		{
  64. 			M[index] = INF;
  65. 			return INF;
  66. 		}
  67. 		else
  68. 		{
  69. 			M[index] = 1;
  70. 			return 1;
  71. 		}
  72. 	}
  73.  
  74. 	if(s[p] == '.')
  75. 	{
  76. 		int b = 0;
  77.  
  78. 		int oo = poc(p+1,o+1,z);
  79. 		//		printf("%d,%d,%d    %d\n",p+1,o+1,z,oo);
  80.  
  81.  
  82. 		int zz = poc(p+1,o,z+1);
  83. 		//		printf("%d,%d,%d    %d\n",p+1,o,z+1,zz);
  84.  
  85.  
  86. 		if(oo != INF)
  87. 			b += oo;
  88. 		if(zz != INF)
  89. 			b += zz;
  90.  
  91. 		//	printf("p=%d o=%d z=%d oo=%d zz=%d     b=%d\n",p,o,z,oo,zz,b);
  92.  
  93. 		M[index] = b  % MIL2;
  94. 		return b  % MIL2;
  95. 	}
  96. 	else
  97. 	{
  98. 		int c = poc(p+1,o,z); 
  99. 		M[index] = c % MIL2;
  100. 		return c% MIL2;
  101. 	}
  102. }
  103.  
  104. int main()
  105. {
  106. 	while(gets(s))
  107. 	{
  108. 		M.clear();
  109. 		int g = poc(0,0,0);
  110. 		printf("%d\n",(g == -1) ? 0 : g%MIL);
  111. 	}
  112. 	return 0;
  113. }
  114.  
  115.