답안 #673400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
673400	2022-12-20T13:52:54 Z	Farhan_HY	Retro (COCI17_retro)	C++14	5 / 100	91 ms	143512 KB

retro

#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() {
      | ^~~~

Subtask #1

5.0 / 100.0

#	결과	실행 시간	메모리	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