Submission #1293900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293900		saidshikhov	Match (CEOI16_match)	C++20	0 / 100	0 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> 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> opened(26, 0);
    
    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';
        
        if (opened[c] < cnt[c] / 2) {
            // Можем поставить открывающую скобку
            res[i] = '(';
            st.push(i);
            opened[c]++;
        } else {
            // Должны поставить закрывающую
            res[i] = ')';
            if (st.empty() || s[st.top()] != s[i]) {
                fout << -1 << endl;
                return 0;
            }
            st.pop();
        }
    }
    
    // Финальная проверка
    stack<int> final_check;
    for (int i = 0; i < n; i++) {
        if (res[i] == '(') {
            final_check.push(i);
        } else {
            if (final_check.empty() || s[final_check.top()] != s[i]) {
                fout << -1 << endl;
                return 0;
            }
            final_check.pop();
        }
    }
    
    if (!final_check.empty()) {
        fout << -1 << endl;
        return 0;
    }
    
    fout << res << endl;
    return 0;
}

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