oj.uz

Submission #77762

# Submission time Handle Problem Language Result Execution time Memory
77762 2018-09-30T09:07:47 Z triplem5ds Match (CEOI16_match) C++14
100 / 100
 33 ms 13076 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int,int>;
using ll = long long;

const int N = 1e5+5;
const int mod = 1e9 + 7;

int n;
string str;
int b4[N][26];
void solve(int l, int r){
    if(l > r)return;
    if(str[l] == str[r]){
        cout << "(";
        solve(l+1,r-1);
        cout << ")";
        return;
    }
    int to = b4[r][str[l] - 'a'];
    cout << "(";
    solve(l+1,to-1);
    cout << ")";
    solve(to + 1, r);
}
int main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE

    cin >> str; n = str.size();

    stack<int>stk;

    for(int i = 0; i < n; i++){
        if(stk.empty() || str[stk.top()] != str[i])
            stk.push(i);
        else
            stk.pop();
    }
    if(!stk.empty()){
        cout << -1 << '\n';
        return 0;
    }
    memset(b4, -1, sizeof b4);
    for(int i = 2; i < n; i++){

        for(char j = 'a'; j <= 'z'; j++){

            if(str[i] == str[i-1]){
                if(str[i-2] == j)
                    b4[i][j-'a'] = i - 2;
                else
                    b4[i][j-'a'] = b4[i-2][j-'a'];
            }   else {
                int to = b4[i-1][str[i]-'a'] - 1;
                if(to < 0)continue;
                if(str[to] == j)
                    b4[i][j-'a'] = to;
                else
                    b4[i][j-'a'] = b4[to][j-'a'];

            }

        }

    }
    solve(0,n-1);

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10488 KB Output is correct
2 Correct 10 ms 10612 KB Output is correct
3 Correct 2 ms 10612 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10488 KB Output is correct
2 Correct 10 ms 10612 KB Output is correct
3 Correct 2 ms 10612 KB Output is correct
4 Correct 13 ms 10624 KB Output is correct
5 Correct 10 ms 10752 KB Output is correct
6 Correct 10 ms 10752 KB Output is correct
7 Correct 10 ms 10752 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10488 KB Output is correct
2 Correct 10 ms 10612 KB Output is correct
3 Correct 2 ms 10612 KB Output is correct
4 Correct 13 ms 10624 KB Output is correct
5 Correct 10 ms 10752 KB Output is correct
6 Correct 10 ms 10752 KB Output is correct
7 Correct 10 ms 10752 KB Output is correct
8 Correct 11 ms 10752 KB Output is correct
9 Correct 11 ms 10832 KB Output is correct
10 Correct 11 ms 10856 KB Output is correct
11 Correct 11 ms 10976 KB Output is correct
12 Correct 19 ms 11672 KB Output is correct
13 Correct 20 ms 12108 KB Output is correct
14 Correct 26 ms 12336 KB Output is correct
15 Correct 33 ms 12788 KB Output is correct
16 Correct 27 ms 12868 KB Output is correct
17 Correct 23 ms 13076 KB Output is correct
18 Correct 24 ms 13076 KB Output is correct
19 Correct 26 ms 13076 KB Output is correct
20 Correct 20 ms 13076 KB Output is correct
21 Correct 26 ms 13076 KB Output is correct