oj.uz

답안 #1111166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1111166 2024-11-11T15:37:24 Z Ghulam_Junaid 괄호 문자열 (CEOI16_match) C++17
10 / 100
 2000 ms 336 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Execution timed out 2067 ms 336 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Execution timed out 2067 ms 336 KB Time limit exceeded
5 Halted 0 ms 0 KB -