Submission #1293894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293894		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> char_count(26, 0);
    for (char c : s) {
        char_count[c - 'a']++;
    }
    
    for (int i = 0; i < 26; i++) {
        if (char_count[i] % 2 != 0) {
            fout << -1 << endl;
            return 0;
        }
    }
    
    string result(n, ' ');
    stack<int> st;
    vector<int> last_used(26, -1);
    
    for (int i = 0; i < n; i++) {
        int char_idx = s[i] - 'a';
        
        if (last_used[char_idx] == -1) {
            // Это первое вхождение символа - ставим открывающую скобку
            result[i] = '(';
            st.push(i);
            last_used[char_idx] = i;
        } else {
            // Это второе вхождение символа
            if (!st.empty() && s[st.top()] == s[i]) {
                // Можем закрыть последнюю открытую скобку с тем же символом
                result[i] = ')';
                st.pop();
                last_used[char_idx] = -1;
            } else {
                // Нужно поставить открывающую скобку
                result[i] = '(';
                st.push(i);
                last_used[char_idx] = i;
            }
        }
    }
    
    // Проверяем, что все скобки закрыты
    if (!st.empty()) {
        fout << -1 << endl;
        return 0;
    }
    
    // Дополнительная проверка: убедимся, что последовательность валидна
    // и удовлетворяет условию на символы
    stack<int> check;
    for (int i = 0; i < n; i++) {
        if (result[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 << result << endl;
    return 0;
}

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