Submission #339689

#	Time	Username	Problem	Language	Result	Execution time	Memory
339689		couplefire	Match (CEOI16_match)	C++17	37 / 100	2076 ms	33864 KiB

match

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

int n; string s;
string ans;

bool solve(int l, int r){
    if(l == r+1) return 1;
    stack<int> st; int good = -1;
    for(int i = l; i<=r; i++){
        if(!st.empty() && st.top() == s[i]-'a') st.pop();
        else st.push(s[i]-'a');
        if(st.empty() && s[i] == s[l]) good = i;
    }
    if(good == -1) return false;
    ans[l] = '('; ans[good] = ')';
    return solve(l+1, good-1)&&solve(good+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);
    if(!solve(0, n-1)) cout << -1 << endl;
    else cout << ans << endl;
}

Compilation message (stderr)

match.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
match.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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