Submission #150493

#	Time	Username	Problem	Language	Result	Execution time	Memory
150493		Little Piplup (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	828 ms	20568 KiB

hiccup

#include "hiccup.h"
#include<bits/stdc++.h>
using std::vector;
using std::cout;
using std::string;
using std::endl;
using std::stack;
int ans(string S) {
   int N = S.size();
   if ( S[0] != 'H' ) return -1;

   vector<int> parse;
   int temp = 0;
   for ( int i = 0 ; i < N ; ++i ) {
      if ( S[i] == 'H' ) {
         if ( temp ) {
            parse.push_back(temp);
            temp = 0;
         }
         parse.push_back(-2);
      } else if ( S[i] == 'C' ) {
         if ( temp ) {
            parse.push_back(temp);
            temp = 0;
         }
         parse.push_back(-1);
      } else {
         ++temp;
      }
   }
   if ( temp ) {
      parse.push_back(temp);
   }

   int size = parse.size();

   int up = N+3, down = 0;
   while( down + 1 < up ) {
      int cur = (up + down)/2;
      //std::cout<<up<<" "<<down<<std::endl;

        stack<int> boo;

      for ( int i = 0 ; i < size ; ++i ) {
         //push current
         boo.push(parse[i]);

         //pop if possible
         while( boo.size() > 2 ){
            int c = boo.top();
            boo.pop();
            int b = boo.top();
            boo.pop();
            int a = boo.top();
            boo.pop();
            
            if ( a == -2 && b == -1 && c >= cur ) {

               if ( boo.empty() || boo.top() == -2 || c == cur) {
                  //do nothing
               } else {      //push back
                  c -= cur;
                  if ( boo.top() == -1 ) {
                     boo.push(c);
                  } else {
                     int temp = boo.top();
                     boo.pop();
                     boo.push(temp+c);
                  }
               }

            } else {
               boo.push(a);
               boo.push(b);
               boo.push(c);
               break;
            }
         }
      }

      if ( boo.empty() ) {
         down = cur;
      } else {
         up = cur;
      }


   }

   return down;
}
int HicCup(string s)
{
   if(ans(s)==0)
   {
        string newstr;
        for(int i=0; i<s.size(); i++)
        {
            newstr.push_back(s[i]);
            if(s[i]=='C')
            {
                newstr.push_back('!');
            }
        }
        if(ans(newstr)==1)
            return 0;
        else
            return -1;
    }
    else
        return ans(s);
}

Compilation message (stderr)

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<s.size(); i++)
                      ~^~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 76 / 76