Source code for submission s1009

Go to diff to previous submission

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. int table[1024][1024];
  39.  
  40.  
  41.  
  42.  
  43. stack_entry make_se(int rem5, int rem10, stack_entry* p) {
  44. stack_entry se;
  45. se._st.rem5 = rem5;
  46. se._st.rem10 = rem10;
  47. se.parent = p;
  48. se.sum = 0;
  49. se.visited = false;
  50. return se;
  51. }
  52.  
  53. //StateTable table;
  54. std::stack<stack_entry> stack;
  55. void do_stuff(){
  56. //table.clear();
  57. for (int i = 0; i < 1024; ++i)
  58. for (int j = 0; j < 1024; ++j){
  59. table[i][j] = -1;
  60. }
  61. stack_entry surface;
  62. surface.sum = 0;
  63.  
  64. table[0][0] = 1;
  65.  
  66. stack.push(make_se(g_Total/2, g_Total/2, &surface));
  67.  
  68. while(!stack.empty())
  69. {
  70.  
  71. stack_entry& top = stack.top();
  72. if ( top.visited ) {
  73.  
  74. table[top._st.rem5][top._st.rem10] = top.sum;
  75. top.parent->sum += top.sum;
  76. top.parent->sum %= 10000000;
  77. stack.pop();
  78. continue;
  79. }
  80. //printf("%d %d\n", top._st.rem5, top._st.rem10);
  81. //STIter rv = table.find(top._st);
  82. if ( table[top._st.rem5][top._st.rem10] != -1) {
  83. top.parent->sum += table[top._st.rem5][top._st.rem10];
  84. top.parent->sum %= 10000000;
  85. stack.pop();
  86. } else {
  87. top.visited = true;
  88. int rem5 = top._st.rem5;
  89. int rem10 = top._st.rem10;
  90. int pos = g_Total - rem5 - rem10;
  91. int bank = rem10 - rem5;
  92.  
  93. switch(g_Buffer[pos]) {
  94. case '.' :
  95. if ( rem5 > 0 )
  96. stack.push(make_se(rem5-1,rem10, &top));
  97. if ( rem10 > 0 && bank > 0 )
  98. stack.push(make_se(rem5,rem10-1, &top));
  99. break;
  100. case '(' :
  101. if ( rem5 > 0 )
  102. stack.push(make_se(rem5-1,rem10, &top));
  103. break;
  104. case ')' :
  105. if ( bank > 0 && rem10 > 0)
  106. stack.push(make_se(rem5,rem10-1, &top));
  107. }
  108. }
  109. }
  110.  
  111. printf("%d\n", surface.sum % 1000000);
  112.  
  113.  
  114. }
  115.  
  116. //
  117. //
  118. //
  119. int main(int argc, char** argv) {
  120. while(!feof(stdin)) {
  121. g_Buffer[0] = 0;
  122. gets(g_Buffer);
  123. g_Total = strlen(g_Buffer);
  124. if ( g_Total == 0 )
  125. break;
  126. do_stuff();
  127. }
  128.  
  129.  
  130. return (EXIT_SUCCESS);
  131. }
  132.  
  133.  

Diff to submission s902

fq.cpp

--- 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();