oj.uz

Submission #673403

# Submission time Handle Problem Language Result Execution time Memory
673403 2022-12-20T13:56:49 Z Farhan_HY Retro (COCI17_retro) C++14
5 / 100
 99 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) {
        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) {
        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 30 ms 70740 KB Output is correct
2 Incorrect 34 ms 70696 KB Output isn't correct
3 Incorrect 37 ms 70772 KB Token "((())a" doesn't correspond to pattern "[\(\)]{1,100000}"
4 Incorrect 32 ms 70824 KB Integer 0 violates the range [1, 100000]
5 Incorrect 32 ms 70732 KB Integer 0 violates the range [1, 100000]
6 Incorrect 37 ms 71244 KB Integer 0 violates the range [1, 100000]
7 Incorrect 37 ms 71336 KB Integer 0 violates the range [1, 100000]
8 Incorrect 37 ms 71372 KB Integer 0 violates the range [1, 100000]
9 Incorrect 32 ms 70708 KB Token "a" doesn't correspond to pattern "[\(\)]{1,100000}"
10 Incorrect 32 ms 70640 KB Integer 0 violates the range [1, 100000]
11 Runtime error 85 ms 143340 KB Execution killed with signal 11
12 Runtime error 86 ms 143368 KB Execution killed with signal 11
13 Runtime error 88 ms 143312 KB Execution killed with signal 11
14 Runtime error 99 ms 143328 KB Execution killed with signal 11
15 Runtime error 85 ms 143396 KB Execution killed with signal 11
16 Runtime error 92 ms 143360 KB Execution killed with signal 11
17 Runtime error 86 ms 143300 KB Execution killed with signal 11
18 Runtime error 89 ms 143308 KB Execution killed with signal 11
19 Runtime error 85 ms 143372 KB Execution killed with signal 11
20 Runtime error 83 ms 143436 KB Execution killed with signal 11