Submission #299700

#	Time	Username	Problem	Language	Result	Execution time	Memory
299700		Gustav	Match (CEOI16_match)	C++14	37 / 100	2019 ms	632 KiB

match

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vector<int>> vvi;
#define debug(x) cerr << (#x) << " " << (x) << endl;
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()

int n;
string s;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    n = sz(s);

    stack<char> st;
    for(int i = 0; i < n; i++){
        if(!st.empty() && st.top() == s[i]) st.pop();
        else st.push(s[i]);
    }
    if(!st.empty()){
        cout << "-1\n";
        return 0;
    }
    string ans = "";
    for(int i = 0; i < n; i++){
        if(!st.empty() && st.top() == s[i]){
            stack<char> t = st;
            t.push(s[i]);
            for(int j = i+1; j < n; j++){
                if(!t.empty() && t.top() == s[j]) t.pop();
                else t.push(s[j]);
            }
            if(t.empty()){
                st.push(s[i]);
                ans.push_back('(');
            }
            else{
                st.pop();
                ans.push_back(')');
            }
        }
        else{
            st.push(s[i]);
            ans.push_back('(');
        }
    }
    cout << ans << endl;
}

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