| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 673400 |
2022-12-20T13:52:54 Z |
Farhan_HY |
Retro (COCI17_retro) |
C++14 |
|
91 ms |
143512 KB |
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define T int t;cin >> t;while(t--)
#define int long long
#define F first
#define S second
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e6 + 6;
int n, m, dp2[100][100][100];
bool vis[100][100][100];
string s[N], dp[100][100][100];
int can(int i, int j, int k) {
if (i == 1) return k == 0;
if (k == 0) {
if (j - 1 > 0 && s[i - 1][j - 1] == '*') return 1;
if (s[i - 1][j] == '*') return 1;
if (j + 1 <= m && s[i - 1][j + 1] == '*') return 1;
}
int &ret = dp2[i][j][k];
if (ret != -1) return ret;
ret = 0;
if (j - 1 > 0 && s[i - 1][j - 1] != '*') {
if (s[i - 1][j - 1] == '(') ret |= can(i - 1, j - 1, k + 1);
else if (s[i - 1][j - 1] == ')' && k > 0) ret |= can(i - 1, j - 1, k - 1);
else if (s[i - 1][j - 1] == '.') ret |= can(i - 1, j - 1, k);
}
if (j + 1 <= m && s[i - 1][j + 1] != '*') {
if (s[i - 1][j + 1] == '(') ret |= can(i - 1, j + 1, k + 1);
else if (s[i - 1][j + 1] == ')' && k > 0) ret |= can(i - 1, j + 1, k - 1);
else if (s[i - 1][j + 1] == '.') ret |= can(i - 1, j + 1, k);
}
if (s[i - 1][j] != '*') {
if (s[i - 1][j] == '(') ret |= can(i - 1, j, k + 1);
else if (s[i - 1][j] == ')' && k > 0) ret |= can(i - 1, j, k - 1);
else if (s[i - 1][j] == '.') ret |= can(i - 1, j, k);
}
return ret;
}
string Rec(int i, int j, int k) {
if (i == 1) {
if (k == 0) return "";
return "a";
}
if (k == 0) {
if (j - 1 > 0 && s[i - 1][j - 1] == '*') return "";
if (s[i - 1][j] == '*') return "";
if (j + 1 <= m && s[i - 1][j + 1] == '*') return "";
}
string &ret = dp[i][j][k];
ret = 'a';
if (vis[i][j][k]) return ret;
vis[i][j][k] = 1;
if (j - 1 > 0 && s[i - 1][j - 1] != '*') {
if (s[i - 1][j - 1] == ')' && k > 0 && can(i - 1, j - 1, k - 1))
ret = min(ret, ')' + Rec(i - 1, j - 1, k - 1));
else if (s[i - 1][j - 1] == '(' && can(i - 1, j - 1, k + 1))
ret = min(ret, '(' + Rec(i - 1, j - 1, k + 1));
else if (s[i][j - 1] == '.' && can(i - 1, j - 1, k))
ret = min(ret, Rec(i - 1, j - 1, k));
}
if (s[i - 1][j] != '*') {
if (s[i - 1][j] == ')' && k > 0 && can(i - 1, j, k - 1))
ret = min(ret, ')' + Rec(i - 1, j, k - 1));
else if (s[i - 1][j] == '(' && can(i - 1, j, k + 1))
ret = min(ret, '(' + Rec(i - 1, j, k + 1));
else if (s[i - 1][j + 1] == '.' && can(i - 1, j, k))
ret = min(ret, Rec(i - 1, j, k));
}
if (j + 1 <= m && s[i - 1][j + 1] != '*') {
if (s[i - 1][j + 1] == ')' && k > 0 && can(i - 1, j + 1, k - 1))
ret = min(ret, ')' + Rec(i - 1, j + 1, k - 1));
else if (s[i - 1][j + 1] == '(' && can(i - 1, j + 1, k + 1))
ret = min(ret, '(' + Rec(i - 1, j + 1, k + 1));
else if (s[i - 1][j + 1] == '.' && can(i - 1, j + 1, k))
ret = min(ret, Rec(i - 1, j + 1, k));
}
return ret;
}
main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> s[i], s[i] = '.' + s[i];
string ans;
memset(dp2, -1, sizeof dp2);
for(int j = 1; j <= m; j++) {
if (s[n][j] == 'M') {
ans = Rec(n, j, 0);
}
}
cout << ans.size() << '\n' << ans;
}
Compilation message
retro.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
83 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
70740 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
70728 KB |
Output isn't correct |
| 3 |
Incorrect |
35 ms |
70864 KB |
Token "((())a" doesn't correspond to pattern "[\(\)]{1,100000}" |
| 4 |
Incorrect |
31 ms |
70740 KB |
Integer 0 violates the range [1, 100000] |
| 5 |
Incorrect |
30 ms |
70732 KB |
Integer 0 violates the range [1, 100000] |
| 6 |
Incorrect |
35 ms |
71252 KB |
Integer 0 violates the range [1, 100000] |
| 7 |
Incorrect |
38 ms |
71260 KB |
Integer 0 violates the range [1, 100000] |
| 8 |
Incorrect |
31 ms |
70716 KB |
Integer 0 violates the range [1, 100000] |
| 9 |
Incorrect |
31 ms |
70680 KB |
Token "a" doesn't correspond to pattern "[\(\)]{1,100000}" |
| 10 |
Incorrect |
31 ms |
70660 KB |
Integer 0 violates the range [1, 100000] |
| 11 |
Runtime error |
88 ms |
143444 KB |
Execution killed with signal 11 |
| 12 |
Incorrect |
33 ms |
70816 KB |
Integer 0 violates the range [1, 100000] |
| 13 |
Runtime error |
83 ms |
143372 KB |
Execution killed with signal 11 |
| 14 |
Incorrect |
33 ms |
70724 KB |
Integer 0 violates the range [1, 100000] |
| 15 |
Incorrect |
34 ms |
70844 KB |
Integer 0 violates the range [1, 100000] |
| 16 |
Incorrect |
34 ms |
70800 KB |
Integer 0 violates the range [1, 100000] |
| 17 |
Runtime error |
84 ms |
143452 KB |
Execution killed with signal 11 |
| 18 |
Incorrect |
33 ms |
70852 KB |
Integer 0 violates the range [1, 100000] |
| 19 |
Runtime error |
85 ms |
143512 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
91 ms |
143436 KB |
Execution killed with signal 11 |
