oj.uz

Submission #77761

# Submission time Handle Problem Language Result Execution time Memory
77761 2018-09-30T09:06:01 Z triplem5ds Match (CEOI16_match) C++14
10 / 100
 2000 ms 70576 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][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 11 ms 10664 KB Output is correct
3 Correct 2 ms 10664 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10488 KB Output is correct
2 Correct 11 ms 10664 KB Output is correct
3 Correct 2 ms 10664 KB Output is correct
4 Execution timed out 2076 ms 70576 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10488 KB Output is correct
2 Correct 11 ms 10664 KB Output is correct
3 Correct 2 ms 10664 KB Output is correct
4 Execution timed out 2076 ms 70576 KB Time limit exceeded
5 Halted 0 ms 0 KB -