Source code for submission s902

fq.cpp

  1. //
  2. // File: fq.cc
  3. // Author: cteam019
  4. //
  5. // Created on October 19, 2013, 12:23 PM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <cstdio>
  10. #include <cstring>
  11. #include <stack>
  12. #include <algorithm>
  13. #include <map>
  14.  
  15. struct state{
  16. int rem5; int rem10;
  17. };
  18.  
  19. struct stack_entry{
  20. state _st;
  21. stack_entry* parent;
  22. int sum;
  23. bool visited;
  24. };
  25.  
  26. struct state_less{
  27. bool operator()(const state& a, const state& b){
  28. return a.rem5 < b.rem5 || ( a.rem5 == b.rem5 && a.rem10 < b.rem10);
  29. }
  30. };
  31.  
  32. typedef std::map<state, int, state_less> StateTable;
  33. typedef StateTable::iterator STIter;
  34.  
  35. char g_Buffer[1024];
  36. //char g_Buffer[] = {"...."};
  37. int g_Total;
  38.  
  39.  
  40. stack_entry make_se(int rem5, int rem10, stack_entry* p) {
  41. stack_entry se;
  42. se._st.rem5 = rem5;
  43. se._st.rem10 = rem10;
  44. se.parent = p;
  45. se.sum = 0;
  46. se.visited = false;
  47. return se;
  48. }
  49.  
  50. void do_stuff(){
  51. StateTable table;
  52. std::stack<stack_entry> stack;
  53.  
  54. stack_entry surface;
  55. surface.sum = 0;
  56.  
  57. state s;
  58. s.rem5 = 0, s.rem10 = 0;
  59. table[s] = 1;
  60.  
  61. stack.push(make_se(g_Total/2, g_Total/2, &surface));
  62.  
  63. while(!stack.empty())
  64. {
  65.  
  66. stack_entry& top = stack.top();
  67. if ( top.visited ) {
  68. table[top._st] = top.sum;
  69. top.parent->sum += top.sum;
  70. top.parent->sum %= 10000000;
  71. stack.pop();
  72. continue;
  73. }
  74.  
  75. STIter rv = table.find(top._st);
  76. if ( rv != table.end() ) {
  77. int val = rv->second;
  78. top.parent->sum += rv->second;
  79. top.parent->sum %= 10000000;
  80. stack.pop();
  81. } else {
  82. top.visited = true;
  83. int rem5 = top._st.rem5;
  84. int rem10 = top._st.rem10;
  85. int pos = g_Total - rem5 - rem10;
  86. int bank = rem10 - rem5;
  87.  
  88. switch(g_Buffer[pos]) {
  89. case '.' :
  90. if ( rem5 > 0 )
  91. stack.push(make_se(rem5-1,rem10, &top));
  92. if ( rem10 > 0 && bank > 0 )
  93. stack.push(make_se(rem5,rem10-1, &top));
  94. break;
  95. case '(' :
  96. if ( rem5 > 0 )
  97. stack.push(make_se(rem5-1,rem10, &top));
  98. break;
  99. case ')' :
  100. if ( bank > 0 && rem10 > 0)
  101. stack.push(make_se(rem5,rem10-1, &top));
  102. }
  103. }
  104. }
  105.  
  106. printf("%d\n", surface.sum % 1000000);
  107.  
  108.  
  109. }
  110.  
  111. //
  112. //
  113. //
  114. int main(int argc, char** argv) {
  115. while(!feof(stdin)) {
  116. g_Buffer[0] = 0;
  117. gets(g_Buffer);
  118. g_Total = strlen(g_Buffer);
  119. if ( g_Total == 0 )
  120. break;
  121. do_stuff();
  122. }
  123.  
  124.  
  125. return (EXIT_SUCCESS);
  126. }
  127.  
  128.