Submission #341618

#	Time	Username	Problem	Language	Result	Execution time	Memory
341618		phathnv	Match (CEOI16_match)	C++11	37 / 100	2083 ms	748 KiB

match

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 1;
const int AL = 26;

int n, answer[N];
string s;

void readInput(){
    cin >> s;
    n = s.size();
    s = '*' + s;
}

bool check(){
    stack <int> st;
    for(int i = 1; i <= n; i++)
        if (answer[i] != -1){
            if (answer[i] == 1)
                st.push(i);
            else if (!st.empty() && s[st.top()] == s[i])
                st.pop();
            else
                return 0;
        } else {
            if (!st.empty() && s[st.top()] == s[i])
                st.pop();
            else
                st.push(i);
        }
    return st.empty();
}

void solve(){
    for(int i = 1; i <= n; i++)
        answer[i] = -1;
    if (!check()){
        cout << -1;
        return;
    }
    for(int i = 1; i <= n; i++){
        answer[i] = 1;
        answer[i] = check();
    }
    for(int i = 1; i <= n; i++)
        cout << (answer[i] == 1? '(' : ')');
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    readInput();
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 63