oj.uz

Submission #500380

# Submission time Handle Problem Language Result Execution time Memory
500380 2021-12-30T19:53:57 Z SirCovidThe19th Match (CEOI16_match) C++17
0 / 100
 6 ms 10444 KB 
#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)

int n, dp[100005][26]; string s; char ans[100005];

void solve(int l, int r){
    if (l > r) return;
    int pt = dp[r][s[l] - 'a']; //[l, pt] [pt + 1, r]

    ans[l] = '('; ans[pt] = ')';
    ans[pt + 1] = '('; ans[r] = ')';

    solve(l + 1, pt - 1); solve(pt + 2, r - 1);
}

int main(){
    cin >> s; n = s.size(); 
    
    stack<int> stk;
    FOR(i, 0, n){
        if (stk.empty() or s[stk.top()] != s[i]) stk.push(i);
        else stk.pop();
    }
    if (!stk.empty()){ cout<<-1<<"\n"; return 0; }

    memset(dp, -1, sizeof(dp));
    FOR(i, 0, n) FOR(c, 0, 26){
        if (s[i] - 'a' == c) dp[i][c] = i; 
        else if (i){
            int l = dp[i - 1][s[i] - 'a']; //[l, i] is good
            if (l > 0) dp[i][c] = dp[l - 1][c];
        }
    }
    solve(0, n - 1);
    FOR(i, 0, n) cout<<ans[i];
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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