oj.uz

Submission #589179

# Submission time Handle Problem Language Result Execution time Memory
589179 2022-07-04T10:02:58 Z andrei_boaca Match (CEOI16_match) C++14
10 / 100
 5 ms 9792 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int n;
string s,sol;
stack<char> st;
vector<int> mypoz[31],v;
set<int> par[100005],imp[100005];
map<vector<int>,int> nrm;
int nxt[100005];
int sum[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    n=s.size();
    s=" "+s;
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.top()==s[i])
            st.pop();
        else
            st.push(s[i]);
    }
    if(!st.empty())
    {
        cout<<-1;
        return 0;
    }
    sol.resize(n+1);
    v.resize(26);
    int nr=1;
    nrm[v]=nr;
    sum[0]=nr;
    for(int i=1;i<=n;i++)
    {
        int p=s[i]-'a';
        if(i%2==1)
            v[p]++;
        else
            v[p]--;
        if(nrm.count(v)==0)
        {
            nr++;
            nrm[v]=nr;
        }
        sum[i]=nrm[v];
    }
    for(int i=1;i<=n;i++)
        if(sol[i]!=')')
        {
            sol[i]='(';
            int poz=0;
            for(int j=i+1;j<=n;j+=2)
            {
                if(sol[j]==')')
                    break;
                if(j%2!=i%2&&sum[i-1]==sum[j]&&s[i]==s[j])
                    poz=j;
            }
            sol[poz]=')';
        }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9724 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9724 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9724 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -