# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
115749 |
2019-06-08T20:11:14 Z |
Breno_XD |
Retro (COCI17_retro) |
C++14 |
|
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 |