oj.uz

Submission #874929

# Submission time Handle Problem Language Result Execution time Memory
874929 2023-11-18T06:25:06 Z Faisal_Saqib Match (CEOI16_match) C++17
0 / 100
 0 ms 348 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;
    for(int j=0;j<n;j++)
    {
        string cur=ans;
        for(int i=0;i<n;i++)
        {
            if(i==j)
            {
                cp1[s[i]-'a'].push_back(i);
                continue;
            }
            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 348 KB Output is correct
2 Incorrect 0 ms 348 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 348 KB Output is correct
2 Incorrect 0 ms 348 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 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -