Submission #588318

#	Time	Username	Problem	Language	Result	Execution time	Memory
588318		web	Match (CEOI16_match)	C++17	37 / 100	2055 ms	584 KiB

match

#include <iostream>
#include <string>
#include <vector>
#include <queue>

#include <stack>
using namespace std;

bool isValidSubS(int beg, int end, string& s, stack<char>& init)
{
    stack<char> opens = init;
    for(int i = beg; i<=end; ++i)
    {
        if(opens.empty())
        {
            opens.push(s[i]);
        }
        else
        {
            if(opens.top() == s[i])
            {
                opens.pop();
            }
            else
            {
                opens.push(s[i]);
            }
        }
    }
    return opens.empty();
}

string findKlammern(string& s)
{
    stack<char> opens;
    string klammern;
    for(int i = 0; i<s.length(); ++i)
    {
        //cout<<"curr state: "<<klammern<<endl;
        opens.push(s[i]);
        if(!isValidSubS(i+1, s.length() -1, s, opens))
        {
            //cout<<"we gotta close, not valid subseq"<<endl;
            opens.pop();
            if(opens.empty())
                {
                    //cout<<"but nothing is open"<<endl;
                    return "1";
                }
            else
            {
                if(opens.top() != s[i])
                   {//cout<<"but we would habe to clos a different kind, "<<opens.top()<<endl; 
                   return "1";

                   }
                
            }
            klammern += ')';
            opens.pop();
        }
        else
        {
            //cout<<"added open"<<endl;
            klammern += '(';
        }
    }
    return klammern;
}
int main()
{
    string s; cin>>s;
    vector<pair<int,int>> letters(26);
    for(int i = 0; i<s.length(); ++i)
    {
        letters[s[i]-97].first++;
    }
    for(auto el: letters)
    {
        if(el.first & 1)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    //else build smallest
    string finalOutput;
    finalOutput = findKlammern(s);
    if(finalOutput.find('1') != string::npos)
    {
        cout<<-1<<endl;
        return 0;
    }
    cout<<finalOutput<<endl;
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'std::string findKlammern(std::string&)':
match.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i<s.length(); ++i)
      |                    ~^~~~~~~~~~~
match.cpp: In function 'int main()':
match.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i<s.length(); ++i)
      |                    ~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 63