Submission #1293911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293911		saidshikhov	Match (CEOI16_match)	C++17	0 / 100	1 ms	332 KiB

match

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

string solve(string s) {
    int n = s.length();
    if (n == 0) return "";
    
    // Невозможно для нечетной длины
    if (n % 2 != 0) return "-1";
    
    // Считаем частоты символов
    vector<int> cnt(26, 0);
    for (char c : s) cnt[c - 'a']++;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] % 2 != 0) return "-1";
    }
    
    // Ищем самую правую позицию, где мы можем поставить закрывающую скобку
    // для первого символа
    vector<int> temp_cnt(26, 0);
    char first_char = s[0];
    
    for (int i = n - 1; i >= 1; i--) {
        if (s[i] == first_char) {
            // Проверяем, можем ли мы использовать эту позицию как закрывающую
            // Для этого оставшаяся часть должна делиться на правильные последовательности
            
            string inside = s.substr(1, i - 1);
            string right = s.substr(i + 1);
            
            string inside_res = solve(inside);
            string right_res = solve(right);
            
            if (inside_res != "-1" && right_res != "-1") {
                return "(" + inside_res + ")" + right_res;
            }
        }
    }
    
    return "-1";
}

int main() {
    ifstream fin("match.in");
    ofstream fout("match.out");
    
    string s;
    fin >> s;
    
    string result = solve(s);
    fout << result << endl;
    
    return 0;
}

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