Source code for submission s1026

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 && 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);
		FOR(i,0,N) M[i].clear();
 
		int g = poc(0,0,0);
		printf("%d\n",(g == -1) ? 0 : g%MIL);
	}
	return 0;
}
 
 

Diff to submission s964

--- c5.s964.cteam079.fq.cpp.0.fq.cpp
+++ c5.s1026.cteam079.fq.cpp.0.fq.cpp
@@ -29,26 +29,29 @@
 
 #define MAX 1005
-#define MAX2 505
 
-map<ll, int> M;
+map<int, int> M[MAX];
 
-ll toH(int a, int b, int c)
+int N;
+
+int toH(int o, int z)
 {
-        return ((ll) c) + (ll)b*1000L + (ll)a * 1000000L;
+        return o*1000 + z;
 }
 
 int poc(int p, int o, int z)
 {
-        ll index = toH(p,o,z);
-
-        if (M.find(index) != M.end())
-                return M[index];
-
         if(z>o)
         {
-                M[index] = INF;
                 return INF;
         }
 
+//      if (p > N/2 && 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++;
@@ -63,10 +66,10 @@
                 if(z != o || s[p] == '(')
                 {
-                        M[index] = INF;
+                        M[p][index] = INF;
                         return INF;
                 }
                 else
                 {
-                        M[index] = 1;
+                        M[p][index] = 1;
                         return 1;
                 }
@@ -92,5 +95,5 @@
                 //      printf("p=%d o=%d z=%d oo=%d zz=%d     b=%d\n",p,o,z,oo,zz,b);
 
-                M[index] = b  % MIL2;
+                M[p][index] = b  % MIL2;
                 return b  % MIL2;
         }
@@ -98,5 +101,5 @@
         {
                 int c = poc(p+1,o,z); 
-                M[index] = c % MIL2;
+                M[p][index] = c % MIL2;
                 return c% MIL2;
         }
@@ -107,5 +110,7 @@
         while(gets(s))
         {
-                M.clear();
+                N = (int) strlen(s);
+                FOR(i,0,N) M[i].clear();
+
                 int g = poc(0,0,0);
                 printf("%d\n",(g == -1) ? 0 : g%MIL);