oj.uz

Submission #500382

# Submission time Handle Problem Language Result Execution time Memory
500382 2021-12-30T19:57:09 Z SirCovidThe19th Match (CEOI16_match) C++17
100 / 100
 22 ms 12856 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 matches with pt
    ans[l] = '('; ans[pt] = ')';
    solve(l + 1, pt - 1); solve(pt + 1, r);
}

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 5 ms 10444 KB Output is correct
3 Correct 1 ms 304 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10444 KB Output is correct
2 Correct 5 ms 10444 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 4 ms 10444 KB Output is correct
5 Correct 4 ms 10444 KB Output is correct
6 Correct 5 ms 10444 KB Output is correct
7 Correct 4 ms 10444 KB Output is correct
8 Correct 5 ms 10416 KB Output is correct
9 Correct 5 ms 10548 KB Output is correct
10 Correct 5 ms 10540 KB Output is correct
11 Correct 6 ms 10668 KB Output is correct
12 Correct 11 ms 11700 KB Output is correct
13 Correct 17 ms 11852 KB Output is correct
14 Correct 14 ms 12228 KB Output is correct
15 Correct 15 ms 12772 KB Output is correct
16 Correct 14 ms 12852 KB Output is correct
17 Correct 14 ms 12856 KB Output is correct
18 Correct 16 ms 11736 KB Output is correct
19 Correct 22 ms 12068 KB Output is correct
20 Correct 15 ms 11888 KB Output is correct
21 Correct 18 ms 12476 KB Output is correct