oj.uz

Submission #571863

# Submission time Handle Problem Language Result Execution time Memory
571863 2022-06-02T22:40:35 Z FerThugGato12500 Match (CEOI16_match) C++17
37 / 100
 2000 ms 852 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 20 ms 316 KB Output is correct
5 Correct 24 ms 212 KB Output is correct
6 Correct 37 ms 332 KB Output is correct
7 Correct 107 ms 332 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 20 ms 316 KB Output is correct
5 Correct 24 ms 212 KB Output is correct
6 Correct 37 ms 332 KB Output is correct
7 Correct 107 ms 332 KB Output is correct
8 Correct 1555 ms 352 KB Output is correct
9 Correct 1598 ms 360 KB Output is correct
10 Correct 1350 ms 348 KB Output is correct
11 Correct 1034 ms 480 KB Output is correct
12 Execution timed out 2089 ms 852 KB Time limit exceeded
13 Halted 0 ms 0 KB -