Source code for submission s964

Go to diff to previous submission

fq.cpp

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

Diff to submission s962

fq.cpp

--- c5.s962.cteam079.fq.cpp.0.fq.cpp
+++ c5.s964.cteam079.fq.cpp.0.fq.cpp
@@ -5,4 +5,5 @@
 #include<ctype.h>
 #include<math.h>
+#include<string.h>
 
 #include<vector>