Source code for submission s1154

Go to diff to previous submission

bugs.cpp

  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7.  
  8. #define stackInit if (!stack.size()) { stack.push_back(0); stackTop = stack.rbegin(); emptyStack = true; }
  9. #define stackPop(x) stack.pop_back(); if (stack.size()) { stackTop = stack.rbegin(); } else if(x) { stackInit; }
  10. #define stackPush(x) stack.push_back(x); stackTop = stack.rbegin();
  11.  
  12. #define putc(x) putc(x, stdout)
  13. //#define getc() fgetc(in)
  14. #define getc() getc(stdin)
  15. typedef unsigned int uint;
  16. using namespace std;
  17.  
  18. uint lines;
  19. string err;
  20. char firstC = 0;
  21. bool repeated;
  22. uint prefixLen;
  23. bool prefixOnly;
  24. vector<uint> stack;
  25. bool emptyStack;
  26. vector<uint>::reverse_iterator stackTop;
  27. vector<pair<uint, uint> > toDoStack; //From - to
  28.  
  29. void printAllToDo() {
  30. for (vector<pair<uint, uint> >::reverse_iterator it = toDoStack.rbegin(); it != toDoStack.rend(); it ++) {
  31. for (uint j = it->first; j < it->second; j ++) {
  32. putc(err[j]);
  33. }
  34. }
  35. toDoStack.clear();
  36. }
  37.  
  38. void printAll() {
  39. for (vector<uint>::iterator it = stack.begin(); it != stack.end(); it ++) {
  40. for (uint j = 0; j < *it; j ++) {
  41. putc(err[j]);
  42. }
  43. }
  44. stack.clear();
  45. stackInit;
  46. }
  47. inline void letterMatch() {
  48. (*stackTop)++;
  49. if (*stackTop == err.size()) { //Found BUG
  50. stackPop(true);
  51. }
  52. }
  53.  
  54. bool apply(char c, bool dontFork) {
  55. if (*stackTop > 0) {
  56. if (c == firstC && !dontFork && !prefixOnly && *stackTop >= prefixLen) {
  57. if (*stackTop == prefixLen) {
  58. *stackTop = 1;
  59. stackPush(prefixLen);
  60. }
  61. else stackPush(1);
  62. return true;
  63. }
  64. else if (c == err[*stackTop]) {
  65. letterMatch();
  66. return true;
  67. }
  68. }
  69. else if (c == firstC) { //Start new one
  70. emptyStack = false;
  71. letterMatch();
  72. return true;
  73. }
  74. return false;
  75. }
  76.  
  77.  
  78. int main()
  79. {
  80. //FILE* in = fopen("bugs.in", "r");
  81. while(true) {
  82. set<char> letters;
  83. //if (fscanf(in, "%u", &lines) != 1) return 0;
  84. if (scanf("%u", &lines) != 1) return 0;
  85. if (getc() < 0) return 0; //space
  86. firstC = 0;
  87. repeated = false;
  88. prefixLen = 0;
  89. prefixOnly = true;
  90. for (char c = getc(); c != '\n'; c = getc()) {
  91. if (c < 0) return 0;
  92. err.push_back(c);
  93. letters.insert(c);
  94. if (!firstC) firstC = c;
  95. else if (firstC == c) repeated = true;
  96. if (prefixOnly) {
  97. if (firstC == c) prefixLen ++;
  98. else prefixOnly = false;
  99. }
  100. }
  101. printf("%s", err.c_str());
  102. stackInit;
  103. pair<uint, uint> tmpPair = make_pair(0, 0);
  104. char c;
  105. for (uint i = 0; i < lines; i += (c == '\n' ? 1 : 0)) {
  106. c = getc();
  107. if (c < 0) return 0;
  108. bool wasFromStack = false;
  109. do {
  110. bool fromStack = toDoStack.size();
  111. const pair<uint, uint> &back = (fromStack ? toDoStack.back() : tmpPair );
  112. char d = (fromStack ? err[back.first] : c);
  113. if (apply(d, fromStack && back.first == 0)) { //Applied - good
  114. if (fromStack) {
  115. if ((back.first + 1) == back.second) { //Finished whole word
  116. toDoStack.pop_back();
  117. }
  118. else {
  119. toDoStack.rbegin()->first ++; //Increment if you did not
  120. }
  121. }
  122. else wasFromStack = false;
  123. continue;
  124. }
  125. if (emptyStack) {
  126. putc(c);
  127. continue;
  128. }
  129. if (stack.size()) { //Did not applied
  130. if (repeated) { //Need toDoStack
  131. if (letters.find(c) == letters.end()) {
  132. printAll();
  133. putc(c);
  134. wasFromStack = false;
  135. }
  136. else {
  137. toDoStack.push_back(make_pair(0, *stackTop));
  138. stackPop(false);
  139. if (!stack.size()) {
  140. printAllToDo();
  141. putc(c);
  142. stackInit;
  143. wasFromStack = false;
  144. }
  145. else wasFromStack = true;
  146. }
  147. }
  148. else { //Do not need toDo stack
  149. printAll();
  150. putc(c);
  151. wasFromStack = false;
  152. }
  153.  
  154. }
  155. } while (toDoStack.size() || wasFromStack);
  156. fflush(stdout);
  157. }
  158. err.clear();
  159. }
  160.  
  161. return 0;
  162. }
  163.  

Diff to submission s1077

bugs.cpp

--- c4.s1077.cteam093.bugs.cpp.0.bugs.cpp
+++ c4.s1154.cteam093.bugs.cpp.0.bugs.cpp
@@ -8,5 +8,5 @@
 #define stackInit if (!stack.size()) { stack.push_back(0); stackTop = stack.rbegin(); emptyStack = true; }
 #define stackPop(x) stack.pop_back(); if (stack.size()) { stackTop = stack.rbegin(); } else if(x) { stackInit; }
-#define stackPush(x) stack.push_back(x); if (stack.size()) { stackTop = stack.rbegin(); } else stackInit;
+#define stackPush(x) stack.push_back(x); stackTop = stack.rbegin();
 
 #define putc(x) putc(x, stdout)
@@ -20,4 +20,6 @@
 char firstC = 0;
 bool repeated;
+uint prefixLen;
+bool prefixOnly;
 vector<uint> stack;
 bool emptyStack;
@@ -52,6 +54,10 @@
 bool apply(char c, bool dontFork) {
     if (*stackTop > 0) {
-        if (c == firstC && !dontFork) {
-            stackPush(1);
+        if (c == firstC && !dontFork && !prefixOnly && *stackTop >= prefixLen) {
+            if (*stackTop == prefixLen) {
+                *stackTop = 1;
+                stackPush(prefixLen);
+            }
+            else stackPush(1);
             return true;
         }
@@ -80,4 +86,6 @@
         firstC = 0;
         repeated = false;
+        prefixLen = 0;
+        prefixOnly = true;
         for (char c = getc(); c != '\n'; c = getc()) {
             if (c < 0) return 0;
@@ -86,5 +94,10 @@
             if (!firstC) firstC = c;
             else if (firstC == c) repeated = true;
+            if (prefixOnly) {
+                if (firstC == c) prefixLen ++;
+                else prefixOnly = false;
+            }
         }
+        printf("%s", err.c_str());
         stackInit;
         pair<uint, uint> tmpPair = make_pair(0, 0);
@@ -141,4 +154,5 @@
                 }
             } while (toDoStack.size() || wasFromStack);
+            fflush(stdout);
         }
         err.clear();