제출 #1111166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111166		Ghulam_Junaid	괄호 문자열 (CEOI16_match)	C++17	10 / 100	2067 ms	336 KiB

match

#include <bits/stdc++.h>
using namespace std;
 
const int T = 26;
const int N = 2e3 + 10;
vector<int> inds[T];
string s;
int n, match[N];
 
bool recur(int l, int r){
    if (r < l) return 1;
    if ((r - l + 1) & 1) return 0;
 
    for (int i=r; i>l; i--){
        if (s[l] == s[i]){
            bool ans1 = recur(l + 1, i - 1);
            bool ans2 = recur(i + 1, r);
            
            if (ans1 && ans2){
                match[l] = i;
                match[i] = l;
                return 1;
            }
 
            if (ans1 || ans2)
                return 0;
        }
    }
    return 0;
}
 
int main(){
    cin >> s;
    n = s.size();
 
    for (int i=0; i<n; i++)
        inds[s[i] - 'a'].push_back(i);
 
    string ans = "-1";
    if (recur(0, n-1)){
        ans.clear();
        for (int i=0; i<n; i++){
            if (match[i] > i) ans += '(';
            else ans += ')';
        }
    }
    cout << ans << endl;
}

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