Submission #588312

#	Time	Username	Problem	Language	Result	Execution time	Memory
588312		web	Match (CEOI16_match)	C++17	10 / 100	8 ms	304 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> opens;
    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(int beg, int end, string& s)
{
    if(end < beg)
        return "";
    if(s[beg] == s[end])
    {
        return '(' + findKlammern(beg+1, end-1, s) + ')';
    }
    
    //split
    for(int i = end-2; i>= beg+1; --i)
    {
        if(isValidSubS(beg, i, s) && isValidSubS(i+1,end, s ))
        {
            return findKlammern(beg, i, s) + findKlammern(i+1, end, s);
        }
    }
    return "1";
}

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(0, s.length()-1 , s);
    if(finalOutput.find('1') != string::npos)
    {
        cout<<-1<<endl;
        return 0;
    }
    cout<<finalOutput<<endl;
    return 0;
}

Compilation message (stderr)

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

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