Go to diff to previous submission
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<ctype.h> #include<math.h> #include<string.h> #include<vector> #include<map> using namespace std; #define FOR(i,a,b) for(int i=a; i<=b; i++) #define PII pair<int, int> #define MP make_pair #define PB push_back #define SIZE(s) (int)(s).int() #define ll long long #define INF -1 #define MIL 1000000 #define MIL2 10000000 char s[1001]; #define MAX 1005 map<int, int> M[MAX]; int N; int toH(int o, int z) { return o*1000 + z; } int poc(int p, int o, int z) { if(z>o) { return INF; } // if (p > N/2-1 && o>z) return INF; //cout << p << " " << o << " " << z << endl; int index = toH(o,z); if (M[p].find( index ) != M[p].end() ) return M[p][index]; if(s[p] == '(') o++; if(s[p] == ')') z++; if( p == (int) strlen(s) -1) { if(s[p] == '.') z++; if(z != o || s[p] == '(') { M[p][index] = INF; return INF; } else { M[p][index] = 1; return 1; } } if(s[p] == '.') { int b = 0; int oo = poc(p+1,o+1,z); // printf("%d,%d,%d %d\n",p+1,o+1,z,oo); int zz = poc(p+1,o,z+1); // printf("%d,%d,%d %d\n",p+1,o,z+1,zz); if(oo != INF) b += oo; if(zz != INF) b += zz; // printf("p=%d o=%d z=%d oo=%d zz=%d b=%d\n",p,o,z,oo,zz,b); M[p][index] = b % MIL2; return b % MIL2; } else { int c = poc(p+1,o,z); M[p][index] = c % MIL2; return c% MIL2; } } int main() { while(gets(s)) { N = (int) strlen(s); if (N == 0) return 0; FOR(i,0,N) M[i].clear(); int g = poc(0,0,0); printf("%d\n",(g == -1) ? 0 : g%MIL); } return 0; }
--- 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();