Source code for submission s1077

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

Diff to submission s965

bugs.cpp

--- c4.s965.cteam093.bugs.cpp.0.bugs.cpp
+++ c4.s1077.cteam093.bugs.cpp.0.bugs.cpp
@@ -4,4 +4,5 @@
 #include <vector>
 #include <cstdio>
+#include <set>
 
 #define stackInit if (!stack.size()) { stack.push_back(0); stackTop = stack.rbegin(); emptyStack = true; }
@@ -73,4 +74,5 @@
     //FILE* in = fopen("bugs.in", "r");
     while(true) {
+        set<char> letters;
         //if (fscanf(in, "%u", &lines) != 1) return 0;
         if (scanf("%u", &lines) != 1) return 0;
@@ -81,4 +83,5 @@
             if (c < 0) return 0;
             err.push_back(c);
+            letters.insert(c);
             if (!firstC) firstC = c;
             else if (firstC == c) repeated = true;
@@ -113,13 +116,20 @@
                 if (stack.size()) { //Did not applied
                     if (repeated) { //Need toDoStack
-                        toDoStack.push_back(make_pair(0, *stackTop));
-                        stackPop(false);
-                        if (!stack.size()) {
-                            printAllToDo();
+                        if (letters.find(c) == letters.end()) {
+                            printAll();
                             putc(c);
-                            stackInit;
                             wasFromStack = false;
                         }
-                        else wasFromStack = true;
+                        else {
+                            toDoStack.push_back(make_pair(0, *stackTop));
+                            stackPop(false);
+                            if (!stack.size()) {
+                                printAllToDo();
+                                putc(c);
+                                stackInit;
+                                wasFromStack = false;
+                            }
+                            else wasFromStack = true;
+                        }
                     }
                     else { //Do not need toDo stack