oj.uz

Submission #940145

# Submission time Handle Problem Language Result Execution time Memory
940145 2024-03-07T05:58:13 Z 12345678 Match (CEOI16_match) C++17
100 / 100
 8 ms 15304 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int n, dp[nx][30], vl[nx], ans[nx];
string s;
stack<int> st;

void solve(int l, int r)
{
    if (r<l) return;
    ans[dp[r][vl[l]]]=1;
    //cout<<l<<' '<<r<<' '<<dp[r][vl[l]]<<'\n';
    solve(l+1, dp[r][vl[l]]-1);
    solve(dp[r][vl[l]]+1, r);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>s;
    n=s.size();
    for (int i=0; i<n; i++) vl[i+1]=s[i]-'a';
    for (auto x:s)
    {
        if (st.empty()||st.top()!=x) st.push(x);
        else st.pop();
    }
    if (!st.empty()) return cout<<-1, 0;
    for (int i=1; i<=n; i++)
    {
        int p=dp[i-1][vl[i]]-1;
        if (p>=0) for (int j=0; j<26; j++) dp[i][j]=dp[p][j];
        dp[i][vl[i]]=i;
    }
    solve(1, n);
    for (int i=1; i<=n; i++) cout<<(ans[i]?')':'(');
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2648 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 4 ms 10024 KB Output is correct
13 Correct 5 ms 12376 KB Output is correct
14 Correct 5 ms 12512 KB Output is correct
15 Correct 6 ms 12892 KB Output is correct
16 Correct 7 ms 12892 KB Output is correct
17 Correct 7 ms 15304 KB Output is correct
18 Correct 7 ms 13916 KB Output is correct
19 Correct 7 ms 14536 KB Output is correct
20 Correct 5 ms 10328 KB Output is correct
21 Correct 8 ms 14936 KB Output is correct