Submission #115733

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
115733	2019-06-08T19:48:53 Z	Breno_XD	Retro (COCI17_retro)	C++14	5 / 100	500 ms	512 KB

retro

#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 >= 1 && i <= r+1 && 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()){
            for(int i = 0; i < seq.size(); i++){
                if(ans[i] == ')' && seq[i] == '('){
                    ans = seq;
                    break;
                }
            }
        }
        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(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:42:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < seq.size(); i++){
                            ~~^~~~~~~~~~~~
retro.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(seq.size() > tmp)
            ~~~~~~~~~~~^~~~~
retro.cpp:60:9: warning: left operand of comma operator has no effect [-Wunused-value]
     if(i-1, j){
        ~^~
retro.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(seq.size() > tmp)
            ~~~~~~~~~~~^~~~~
retro.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(seq.size() > tmp)
            ~~~~~~~~~~~^~~~~
retro.cpp: In function 'int main()':
retro.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Incorrect	21 ms	384 KB	Output isn't correct
3	Incorrect	120 ms	384 KB	Output isn't correct
4	Incorrect	171 ms	384 KB	Integer 0 violates the range [1, 100000]
5	Incorrect	141 ms	384 KB	Output isn't correct
6	Execution timed out	1071 ms	384 KB	Time limit exceeded
7	Execution timed out	1075 ms	384 KB	Time limit exceeded
8	Execution timed out	1067 ms	384 KB	Time limit exceeded
9	Execution timed out	1071 ms	384 KB	Time limit exceeded
10	Execution timed out	1073 ms	384 KB	Time limit exceeded
11	Execution timed out	1071 ms	512 KB	Time limit exceeded
12	Execution timed out	1083 ms	512 KB	Time limit exceeded
13	Execution timed out	1080 ms	512 KB	Time limit exceeded
14	Execution timed out	1087 ms	512 KB	Time limit exceeded
15	Execution timed out	1072 ms	512 KB	Time limit exceeded
16	Execution timed out	1079 ms	512 KB	Time limit exceeded
17	Execution timed out	1078 ms	512 KB	Time limit exceeded
18	Execution timed out	1079 ms	512 KB	Time limit exceeded
19	Execution timed out	1072 ms	512 KB	Time limit exceeded
20	Execution timed out	1073 ms	512 KB	Time limit exceeded