Source code for submission s1042

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.  
  32. map<int, int> M[MAX];
  33.  
  34. int N;
  35.  
  36. int toH(int o, int z)
  37. {
  38. return o*1000 + z;
  39. }
  40.  
  41. int poc(int p, int o, int z)
  42. {
  43. if(z>o)
  44. {
  45. return INF;
  46. }
  47.  
  48. // if (p > N/2-1 && o>z) return INF;
  49. //cout << p << " " << o << " " << z << endl;
  50.  
  51. int index = toH(o,z);
  52.  
  53. if (M[p].find( index ) != M[p].end() )
  54. return M[p][index];
  55.  
  56. if(s[p] == '(')
  57. o++;
  58. if(s[p] == ')')
  59. z++;
  60.  
  61. if( p == (int) strlen(s) -1)
  62. {
  63. if(s[p] == '.')
  64. z++;
  65.  
  66. if(z != o || s[p] == '(')
  67. {
  68. M[p][index] = INF;
  69. return INF;
  70. }
  71. else
  72. {
  73. M[p][index] = 1;
  74. return 1;
  75. }
  76. }
  77.  
  78. if(s[p] == '.')
  79. {
  80. int b = 0;
  81.  
  82. int oo = poc(p+1,o+1,z);
  83. // printf("%d,%d,%d %d\n",p+1,o+1,z,oo);
  84.  
  85.  
  86. int zz = poc(p+1,o,z+1);
  87. // printf("%d,%d,%d %d\n",p+1,o,z+1,zz);
  88.  
  89.  
  90. if(oo != INF)
  91. b += oo;
  92. if(zz != INF)
  93. b += zz;
  94.  
  95. // printf("p=%d o=%d z=%d oo=%d zz=%d b=%d\n",p,o,z,oo,zz,b);
  96.  
  97. M[p][index] = b % MIL2;
  98. return b % MIL2;
  99. }
  100. else
  101. {
  102. int c = poc(p+1,o,z);
  103. M[p][index] = c % MIL2;
  104. return c% MIL2;
  105. }
  106. }
  107.  
  108. int main()
  109. {
  110. while(gets(s))
  111. {
  112. N = (int) strlen(s);
  113. if (N == 0) return 0;
  114. FOR(i,0,N) M[i].clear();
  115.  
  116. int g = poc(0,0,0);
  117. printf("%d\n",(g == -1) ? 0 : g%MIL);
  118. }
  119. return 0;
  120. }
  121.  
  122.  

Diff to submission s1026

fq.cpp

--- c5.s1026.cteam079.fq.cpp.0.fq.cpp
+++ c5.s1042.cteam079.fq.cpp.0.fq.cpp
@@ -46,5 +46,5 @@
         }
 
-//      if (p > N/2 && o>z) return INF;
+//      if (p > N/2-1 && o>z) return INF;
         //cout << p << " " << o << " " << z << endl;
 
@@ -111,4 +111,5 @@
         {
                 N = (int) strlen(s);
+                if (N == 0) return 0;
                 FOR(i,0,N) M[i].clear();