oj.uz

Submission #874936

# Submission time Handle Problem Language Result Execution time Memory
874936 2023-11-18T06:35:32 Z Faisal_Saqib Match (CEOI16_match) C++17
0 / 100
 0 ms 344 KB 
#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=min(ans,cur);
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -