oj.uz

Submission #588962

# Submission time Handle Problem Language Result Execution time Memory
588962 2022-07-04T08:16:50 Z andrei_boaca Match (CEOI16_match) C++14
37 / 100
 2000 ms 50576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
int n;
string s,sol;
stack<char> st;
bitset<100005> can[100005];
int f[31];
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++)
    {
        while(!st.empty())
            st.pop();
        for(int j=i;j<=n;j++)
        {
            if(!st.empty()&&st.top()==s[j])
                st.pop();
            else
                st.push(s[j]);
            if(st.empty())
                can[i][j]=1;
        }
    }
    if(!can[1][n])
    {
        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+=2)
            {
                if(sol[j]==')')
                    break;
                if(can[i][j]&&s[i]==s[j])
                    if(j==i+1||can[i+1][j-1])
                        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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 2900 KB Output is correct
5 Correct 3 ms 2360 KB Output is correct
6 Correct 7 ms 6212 KB Output is correct
7 Correct 11 ms 6868 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 2900 KB Output is correct
5 Correct 3 ms 2360 KB Output is correct
6 Correct 7 ms 6212 KB Output is correct
7 Correct 11 ms 6868 KB Output is correct
8 Correct 91 ms 18796 KB Output is correct
9 Correct 105 ms 18976 KB Output is correct
10 Correct 108 ms 15736 KB Output is correct
11 Correct 103 ms 15836 KB Output is correct
12 Execution timed out 2095 ms 50576 KB Time limit exceeded
13 Halted 0 ms 0 KB -