제출 #1293888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293888		saidshikhov	괄호 문자열 (CEOI16_match)	C++20	0 / 100	1 ms	332 KiB

match

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

int main() {
    ifstream fin("match.in");
    ofstream fout("match.out");
    
    string s;
    fin >> s;
    int n = s.length();
    
    // Проверка: длина должна быть четной
    if (n % 2 != 0) {
        fout << -1 << endl;
        return 0;
    }
    
    // Проверка: для каждого символа должно быть четное количество
    vector<int> count(26, 0);
    for (char c : s) {
        count[c - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
        if (count[i] % 2 != 0) {
            fout << -1 << endl;
            return 0;
        }
    }
    
    string result(n, ' ');
    vector<int> last_occurrence(26, -1);
    vector<int> pair_count(26, 0);
    
    // Жадное построение
    stack<int> st;  // стек для индексов открытых скобок
    
    for (int i = 0; i < n; i++) {
        char c = s[i];
        int char_idx = c - 'a';
        
        if (last_occurrence[char_idx] == -1) {
            // Первое вхождение символа - должна быть открывающая скобка
            result[i] = '(';
            st.push(i);
            last_occurrence[char_idx] = i;
            pair_count[char_idx]++;
        } else {
            // Второе вхождение символа - проверяем, может ли быть закрывающей
            if (!st.empty() && s[st.top()] == c) {
                // Можем закрыть последнюю открытую скобку с тем же символом
                result[i] = ')';
                st.pop();
                last_occurrence[char_idx] = -1;  // сброс для следующей пары
            } else {
                // Пытаемся найти подходящую открывающую скобку
                bool found = false;
                for (int j = 0; j < 26; j++) {
                    if (last_occurrence[j] != -1 && pair_count[j] < count[j] / 2) {
                        // Можем использовать этот символ для открывающей скобки
                        result[i] = '(';
                        st.push(i);
                        last_occurrence[char_idx] = i;
                        pair_count[char_idx]++;
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    // Должны поставить закрывающую
                    result[i] = ')';
                    if (st.empty()) {
                        fout << -1 << endl;
                        return 0;
                    }
                    // Проверяем, что символы совпадают
                    if (s[st.top()] != c) {
                        fout << -1 << endl;
                        return 0;
                    }
                    st.pop();
                    last_occurrence[s[st.top()] - 'a'] = -1;
                }
            }
        }
    }
    
    // Проверяем, что все скобки закрыты
    if (!st.empty()) {
        fout << -1 << endl;
        return 0;
    }
    
    fout << result << endl;
    
    return 0;
}

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