/* Topcoder SRM 696, D2, 250-Pointer: Ropestring * James S. Plank * Wed Sep 7 09:58:57 EDT 2016 */ #include #include #include #include #include #include using namespace std; class Ropestring { public: string makerope(string s); }; string Ropestring::makerope(string s) { multiset E; multiset O; multiset ::reverse_iterator mit; int dots; int RL; string rv; int i, j; /* Sentinelize s. Account for that by setting dots to -1 */ s.push_back('.'); dots = -1; RL = 0; /* I'm using the first approach of the two that I describe in the writeup. */ for (i = 0; i < s.size(); i++) { /* With dashes, you simply increase the rope length. */ if (s[i] == '-') { RL++; /* With dots, you put the rope string into its proper place, and reset the rope length. */ } else { if (RL > 0) { if (RL % 2 == 1) { O.insert(RL); } else { E.insert(RL); } } RL = 0; dots++; } } /* Create the return string with just dots. I decrement s.size() to account for the sentinel. */ rv.resize(s.size()-1, '.'); i = 0; /* Add all of the roped from E, highest to lowest. */ for (mit = E.rbegin(); mit != E.rend(); mit++) { RL = *mit; for (j = 0; j < RL; j++) rv[j+i] = '-'; i += (RL+1); } /* Add all of the roped from O, highest to lowest. */ for (mit = O.rbegin(); mit != O.rend(); mit++) { RL = *mit; for (j = 0; j < RL; j++) rv[j+i] = '-'; i += (RL+1); } return rv; }