oj.uz

Submission #589193

# Submission time Handle Problem Language Result Execution time Memory
589193 2022-07-04T10:18:11 Z andrei_boaca Match (CEOI16_match) C++14
37 / 100
 2000 ms 42156 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;
vector<char> st;
vector<int> mypoz[31],v;
set<int> par[100005],imp[100005];
map<vector<char>,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;
    }
    int nr=1;
    nrm[st]=1;
    sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.back()==s[i])
            st.pop_back();
        else
            st.push_back(s[i]);
        if(nrm[st]==0)
        {
            nr++;
            nrm[st]=nr;
        }
        sum[i]=nrm[st];
        /*if(st.empty())
            cout<<'-';
        for(char j:st)
            cout<<j<<' ';
        cout<<'\n';*/
    }
    if(!st.empty())
    {
        cout<<-1;
        return 0;
    }
    sol.resize(n+1);
    for(int i=1;i<=n;i++)
        if(sol[i]!=')')
    {
        sol[i]='(';
        int poz=0;
        for(int j=i+1;j<=n;j++)
        {
            if(sol[j]==')')
                break;
            if(j%2!=i%2&&s[j]==s[i]&&sum[i-1]==sum[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 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 7 ms 9724 KB Output is correct
7 Correct 8 ms 9684 KB Output is correct
8 Correct 11 ms 9880 KB Output is correct
9 Correct 134 ms 11160 KB Output is correct
10 Correct 144 ms 11740 KB Output is correct
11 Correct 314 ms 13608 KB Output is correct
12 Execution timed out 2088 ms 42156 KB Time limit exceeded
13 Halted 0 ms 0 KB -