Submission #115749

# Submission time Handle Problem Language Result Execution time Memory
115749 2019-06-08T20:11:14 Z Breno_XD Retro (COCI17_retro) C++14
11 / 100
500 ms 512 KB
#include <bits/stdc++.h>

using namespace std;

#define MAX 310

string seq, ans;
int r, s, x, y;
char v[MAX][MAX];

bool valid(int i, int j){
    if(i >= 0 && i <= r && j >= 1 && j <= s)return true;
    return false;
}

void dfs(int i, int j){

    if(v[i][j] == '*' || (i < 1 && j >= 1 && j <= s)){

        stack<char> pilha;

        bool ok = true;
        for(int i = 0; i < seq.size(); i++){
            if(seq[i] == '('){
                pilha.push('(');
            }else if(seq[i] == ')'){
                if(pilha.size() > 0){
                    pilha.pop();
                }else{
                    ok = false;
                    break;
                }
            }
        }

        if(pilha.size() > 0) ok = false;

        if(ok && seq.size() > ans.size()){
            ans = seq;
        }else if(ok && seq.size() == ans.size()){
            ans = min(ans,seq);
        }
        return;
    }

    seq += v[i][j];

    if(valid(i-1, j-1)){
        int tmp = seq.size();
        dfs(i-1, j-1);
        if(seq.size() > tmp)
            seq.erase(seq.begin()+seq.size()-1);
    }
    if(valid(i-1, j)){
        int tmp = seq.size();
        dfs(i-1, j);
        if(seq.size() > tmp)
            seq.erase(seq.begin()+seq.size()-1);
    }
    if(valid(i-1, j+1)){
        int tmp = seq.size();
        dfs(i-1, j+1);
        if(seq.size() > tmp)
            seq.erase(seq.begin()+seq.size()-1);
    }

    return;

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> r >> s;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= s; j++){
            cin >> v[i][j];
            if(v[i][j] == 'M'){
                x = i; y = j;
            }
        }
    }
    dfs(x, y);
    string ans2 = "";
    for(int i = 0; i < ans.size(); i++){
        if(ans[i] == '(' || ans[i] == ')'){
            ans2 += ans[i];
        }
    }
    cout << ans2.size() << "\n";
    cout << ans2 << "\n";
    /*
    for(int i = 0; i < ans2.size(); i++){
        cout << ans2[i] << " ";
    }
    cout << "\n";
    */
    return 0;
}

Compilation message

retro.cpp: In function 'void dfs(int, int)':
retro.cpp:23:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < seq.size(); i++){
                        ~~^~~~~~~~~~~~
retro.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(seq.size() > tmp)
            ~~~~~~~~~~~^~~~~
retro.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(seq.size() > tmp)
            ~~~~~~~~~~~^~~~~
retro.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(seq.size() > tmp)
            ~~~~~~~~~~~^~~~~
retro.cpp: In function 'int main()':
retro.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 384 KB Partially correct
2 Correct 48 ms 384 KB Output is correct
3 Partially correct 329 ms 384 KB Partially correct
4 Partially correct 426 ms 384 KB Partially correct
5 Incorrect 385 ms 384 KB Output isn't correct
6 Execution timed out 1072 ms 384 KB Time limit exceeded
7 Execution timed out 1068 ms 384 KB Time limit exceeded
8 Execution timed out 1070 ms 384 KB Time limit exceeded
9 Execution timed out 1061 ms 384 KB Time limit exceeded
10 Execution timed out 1073 ms 384 KB Time limit exceeded
11 Execution timed out 1076 ms 512 KB Time limit exceeded
12 Execution timed out 1056 ms 512 KB Time limit exceeded
13 Execution timed out 1063 ms 512 KB Time limit exceeded
14 Execution timed out 1071 ms 512 KB Time limit exceeded
15 Execution timed out 1085 ms 512 KB Time limit exceeded
16 Execution timed out 1076 ms 512 KB Time limit exceeded
17 Execution timed out 1071 ms 512 KB Time limit exceeded
18 Execution timed out 1086 ms 512 KB Time limit exceeded
19 Execution timed out 1074 ms 512 KB Time limit exceeded
20 Execution timed out 1084 ms 512 KB Time limit exceeded