oj.uz

Submission #588312

# Submission time Handle Problem Language Result Execution time Memory
588312 2022-07-03T06:34:48 Z web Match (CEOI16_match) C++17
10 / 100
 8 ms 304 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Incorrect 8 ms 300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Incorrect 8 ms 300 KB Output isn't correct
5 Halted 0 ms 0 KB -