Submission #954409

#	Time	Username	Problem	Language	Result	Execution time	Memory
954409		parlimoos	Match (CEOI16_match)	C++14	0 / 100	512 ms	524288 KiB

match

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

string s , o;
int n;
bool iso = 1;

void f(int l = 0 , int r = n - 1 , int c = 0){
    if(l > r) return;
    vector<int> is;
    for(int i = l ; i <= r ; i++) if(int(s[i] - 'a') == c) is.pb(i);
    if(((int)is.size() & 1)){
        iso = 0;
        return;
    }
    if(is.empty()){
        f(l , r);
        return;
    }
    for(int i = 0 ; i < ((int)is.size() / 2) ; i++) o[is[i]] = '(';
    for(int i = ((int)is.size() / 2) ; i < (int)is.size() ; i++) o[is[i]] = ')';
    f(l , is[0] - 1 , c + 1) , f(is.back() + 1 , r , c + 1);
    for(int i = 0 ; i < (int)is.size() ; i++) f(is[i] + 1 , is[i + 1] - 1 , c + 1);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    n = (int)s.length() , o = s;
    f();
    if(iso) for(int i = 0 ; i < n ; i++) cout << o[i];
    else cout << -1;
}

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