Go to diff to previous submission
// // File: fq.cc // Author: cteam019 // // Created on October 19, 2013, 12:23 PM // #include <stdlib.h> #include <cstdio> #include <cstring> #include <stack> #include <algorithm> #include <map> struct state{ int rem5; int rem10; }; struct stack_entry{ state _st; stack_entry* parent; int sum; bool visited; }; struct state_less{ bool operator()(const state& a, const state& b){ return a.rem5 < b.rem5 || ( a.rem5 == b.rem5 && a.rem10 < b.rem10); } }; typedef std::map<state, int, state_less> StateTable; typedef StateTable::iterator STIter; char g_Buffer[1024]; //char g_Buffer[] = {"...."}; int g_Total; int table[1024][1024]; stack_entry make_se(int rem5, int rem10, stack_entry* p) { stack_entry se; se._st.rem5 = rem5; se._st.rem10 = rem10; se.parent = p; se.sum = 0; se.visited = false; return se; } //StateTable table; std::stack<stack_entry> stack; void do_stuff(){ //table.clear(); for (int i = 0; i < 1024; ++i) for (int j = 0; j < 1024; ++j){ table[i][j] = -1; } stack_entry surface; surface.sum = 0; table[0][0] = 1; stack.push(make_se(g_Total/2, g_Total/2, &surface)); while(!stack.empty()) { stack_entry& top = stack.top(); if ( top.visited ) { table[top._st.rem5][top._st.rem10] = top.sum; top.parent->sum += top.sum; top.parent->sum %= 10000000; stack.pop(); continue; } //printf("%d %d\n", top._st.rem5, top._st.rem10); //STIter rv = table.find(top._st); if ( table[top._st.rem5][top._st.rem10] != -1) { top.parent->sum += table[top._st.rem5][top._st.rem10]; top.parent->sum %= 10000000; stack.pop(); } else { top.visited = true; int rem5 = top._st.rem5; int rem10 = top._st.rem10; int pos = g_Total - rem5 - rem10; int bank = rem10 - rem5; switch(g_Buffer[pos]) { case '.' : if ( rem5 > 0 ) stack.push(make_se(rem5-1,rem10, &top)); if ( rem10 > 0 && bank > 0 ) stack.push(make_se(rem5,rem10-1, &top)); break; case '(' : if ( rem5 > 0 ) stack.push(make_se(rem5-1,rem10, &top)); break; case ')' : if ( bank > 0 && rem10 > 0) stack.push(make_se(rem5,rem10-1, &top)); } } } printf("%d\n", surface.sum % 1000000); } // // // int main(int argc, char** argv) { while(!feof(stdin)) { g_Buffer[0] = 0; gets(g_Buffer); g_Total = strlen(g_Buffer); if ( g_Total == 0 ) break; do_stuff(); } return (EXIT_SUCCESS); }
--- c5.s902.cteam019.fq.cpp.0.fq.cpp +++ c5.s1009.cteam019.fq.cpp.0.fq.cpp @@ -36,4 +36,7 @@ //char g_Buffer[] = {"...."}; int g_Total; +int table[1024][1024]; + + @@ -48,14 +51,16 @@ } -void do_stuff(){ - StateTable table; + //StateTable table; std::stack<stack_entry> stack; - +void do_stuff(){ + //table.clear(); + for (int i = 0; i < 1024; ++i) + for (int j = 0; j < 1024; ++j){ + table[i][j] = -1; +} stack_entry surface; surface.sum = 0; - state s; - s.rem5 = 0, s.rem10 = 0; - table[s] = 1; + table[0][0] = 1; stack.push(make_se(g_Total/2, g_Total/2, &surface)); @@ -66,5 +71,6 @@ stack_entry& top = stack.top(); if ( top.visited ) { - table[top._st] = top.sum; + + table[top._st.rem5][top._st.rem10] = top.sum; top.parent->sum += top.sum; top.parent->sum %= 10000000; @@ -72,9 +78,8 @@ continue; } - - STIter rv = table.find(top._st); - if ( rv != table.end() ) { - int val = rv->second; - top.parent->sum += rv->second; + //printf("%d %d\n", top._st.rem5, top._st.rem10); + //STIter rv = table.find(top._st); + if ( table[top._st.rem5][top._st.rem10] != -1) { + top.parent->sum += table[top._st.rem5][top._st.rem10]; top.parent->sum %= 10000000; stack.pop();