Submission #874937

#	Time	Username	Problem	Language	Result	Execution time	Memory
874937		Faisal_Saqib	괄호 문자열 (CEOI16_match)	C++17	0 / 100	1 ms	348 KiB

match

#include <bits/stdc++.h>
using namespace std;
bool valid(string& s,string& b)
{
    int n=s.size();
    vector<int> cp;
    for(int i=0;i<n;i++)
    {
        if(b[i]=='?')
            return 0;
        if(b[i]=='(')
        {
            cp.push_back(i);
        }
        else if(cp.size()==0)
            return 0;
        else if(s[cp.back()]!=s[i])
            return 0;
        else
            cp.pop_back();
    }
    return (cp.size()==0);
}
int main()
{
    string s;
    cin>>s;
    int n=s.size();
    string ans((size_t)n,')');
    vector<int> cp1[26];
    for(int i=0;i<n;i++)
    {
        if(cp1[s[i]-'a'].size())
        {
            ans[cp1[s[i]-'a'].back()]='(';
            ans[i]=')';
            cp1[s[i]-'a'].pop_back();
        }
        else
            cp1[s[i]-'a'].push_back(i);
    }
    if(!valid(s,ans))
    {
        cout<<-1<<endl;
        exit(0);
    }
    vector<int> cp;
    // cout<<ans<<endl;
    for(int j=0;j<n;j++)
    {
        string cur=ans;
        cur[j]='(';
        for(int i=0;i<=j;i++)
        {
            if(cur[i]=='(')
                cp1[s[i]-'a'].push_back(i);
            else if(cur[i]==')')
                cp1[s[i]-'a'].pop_back();
        }
        for(int i=j+1;i<n;i++)
        {
            if(cp1[s[i]-'a'].size())
            {
                cur[cp1[s[i]-'a'].back()]='(';
                cur[i]=')';
                cp1[s[i]-'a'].pop_back();
            }
            else
                cp1[s[i]-'a'].push_back(i);
        }
        if(valid(s,cur))
            ans=cur;
    }
    cout<<ans<<endl;
    return 0;
}

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