oj.uz

Submission #673404

# Submission time Handle Problem Language Result Execution time Memory
673404 2022-12-20T13:58:03 Z Farhan_HY Retro (COCI17_retro) C++14
5 / 100
 94 ms 143436 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 && i != n) {
        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) return "";
    string &ret = dp[i][j][k];
    ret = 'a';
    if (k == 0 && i != n) {
        if (j - 1 > 0 && s[i - 1][j - 1] == '*') ret = "";
        if (s[i - 1][j] == '*') ret = "";
        if (j + 1 <= m && s[i - 1][j + 1] == '*') ret = "";
    }
    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:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main() {
      | ^~~~

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70732 KB Output is correct
2 Incorrect 36 ms 70708 KB Output isn't correct
3 Incorrect 31 ms 70712 KB Token "((())a" doesn't correspond to pattern "[\(\)]{1,100000}"
4 Incorrect 32 ms 70728 KB Integer 0 violates the range [1, 100000]
5 Incorrect 33 ms 70740 KB Integer 0 violates the range [1, 100000]
6 Incorrect 39 ms 71208 KB Integer 0 violates the range [1, 100000]
7 Incorrect 37 ms 71308 KB Integer 0 violates the range [1, 100000]
8 Incorrect 38 ms 71372 KB Integer 0 violates the range [1, 100000]
9 Incorrect 31 ms 70668 KB Token "a" doesn't correspond to pattern "[\(\)]{1,100000}"
10 Incorrect 33 ms 70740 KB Token "a" doesn't correspond to pattern "[\(\)]{1,100000}"
11 Runtime error 86 ms 143336 KB Execution killed with signal 11
12 Runtime error 84 ms 143368 KB Execution killed with signal 11
13 Runtime error 93 ms 143340 KB Execution killed with signal 11
14 Runtime error 93 ms 143316 KB Execution killed with signal 11
15 Runtime error 89 ms 143408 KB Execution killed with signal 11
16 Runtime error 89 ms 143396 KB Execution killed with signal 11
17 Runtime error 89 ms 143412 KB Execution killed with signal 11
18 Runtime error 87 ms 143324 KB Execution killed with signal 11
19 Runtime error 94 ms 143436 KB Execution killed with signal 11
20 Runtime error 88 ms 143352 KB Execution killed with signal 11