oj.uz

Submission #339682

# Submission time Handle Problem Language Result Execution time Memory
339682 2020-12-25T23:00:40 Z couplefire Match (CEOI16_match) C++17
0 / 100
 1 ms 376 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

int n; string s;
int dp[MAXN];
string ans;

bool solve(int l, int r){
    if(l == r+1) return 1;
    if(dp[l] == -1) return false;
    ans[l] = '('; ans[dp[l]] = ')';
    return solve(l+1, dp[l]-1) && solve(dp[l]+1, r);
}

int main(){
    // freopen("match.in", "r", stdin);
    // freopen("match.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s; n = s.length();
    ans.resize(n);
    dp[n] = -1;
    for(int i = n-1; i>=0; i--){
        dp[i] = -1;
        if(i != n-1 && s[i] == s[i+1]) dp[i] = i+1;
        int cur = i+1;
        while(dp[cur] != -1){
            cur = dp[cur]+1;
            if(cur != n && s[cur] == s[i]) dp[i] = cur;
        }
    }
    if(!solve(0, n-1)) cout << -1 << endl;
    else cout << ans << endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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