Submission #571863

#	Time	Username	Problem	Language	Result	Execution time	Memory
571863		FerThugGato12500	Match (CEOI16_match)	C++17	37 / 100	2089 ms	852 KiB

match

#include<bits/stdc++.h>
using namespace std;

string s, B = "";
int n;
bool poder(string A){

    stack<int> lst;
    int D = 0;

    for(int i = 0; i < n; i++){
        if(D<0) return false;
        if(i<A.size()){
            if(A[i]=='('){ lst.push(i); D++; }
            else{
                if(!lst.size() ||  s[lst.top()]!=s[i]) return false;
                lst.pop();
                D--;
            }
            continue;
        }
        if(!lst.size() || s[lst.top()]!=s[i] ){
            lst.push(i);
            D++;
        }else{
            lst.pop();
            D--;
        }
    }
    return (D==0);
}

int main(){
    cin>>s;
    n = s.size();


    int j = 0;
    while(j<n){
        int ini = 0, fin = n-j;
        while(ini + 1 < fin){
            int mit = (ini + fin) / 2;
            string c = ""; for(int i = 0; i < mit; i++) c+='(';
            if(poder(B + c)){
                ini = mit;
            }else{
                fin = mit-1;
            }
        }
        string c = ""; for(int i = 0; i < fin; i++) c+='(';
        if(poder(B + c)) ini = fin;
        for(int i = 0; i < ini; i++) B+='(';
        B+=')';
        j += ini+1;
    }
    cout << (poder(B) ? B : "-1");
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'bool poder(std::string)':
match.cpp:13:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         if(i<A.size()){
      |            ~^~~~~~~~~

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