제출 #1293898

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

match

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stack>
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> cnt(26, 0);
    for (char c : s) {
        cnt[c - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
        if (cnt[i] % 2 != 0) {
            fout << -1 << endl;
            return 0;
        }
    }
    
    string res(n, '.');
    stack<int> st;
    vector<int> last_pos(26, -1);
    
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        
        if (last_pos[c] == -1) {
            // Первое вхождение символа - пробуем поставить '('
            res[i] = '(';
            st.push(i);
            last_pos[c] = i;
        } else {
            // Второе вхождение символа
            if (!st.empty() && st.top() == last_pos[c]) {
                // Можем закрыть именно парную скобку
                res[i] = ')';
                st.pop();
                last_pos[c] = -1;
            } else {
                // Не можем закрыть - ставим '('
                res[i] = '(';
                st.push(i);
                last_pos[c] = i;
            }
        }
    }
    
    // Проверка валидности
    stack<int> check;
    for (int i = 0; i < n; i++) {
        if (res[i] == '(') {
            check.push(i);
        } else {
            if (check.empty()) {
                fout << -1 << endl;
                return 0;
            }
            int open_idx = check.top();
            check.pop();
            if (s[open_idx] != s[i]) {
                fout << -1 << endl;
                return 0;
            }
        }
    }
    
    if (!check.empty()) {
        fout << -1 << endl;
        return 0;
    }
    
    fout << res << endl;
    return 0;
}

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