oj.uz

Submission #680512

# Submission time Handle Problem Language Result Execution time Memory
680512 2023-01-11T03:54:55 Z vjudge1 parentrises (BOI18_parentrises) C++14
16 / 100
 85 ms 1020 KB 
#include <bits/stdc++.h>
#define ll long long
#define st first
#define nd second
#define pii pair <ll, ll>
#define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
#define rrep(i, n, m) for (ll i = (n); i >= (m); i --)
using namespace std;

namespace P1 {

    int val(char ch) {
        return ch == ')' ? -1 : 1;
    }

    bool dp[111][55][55];
    ll a[111];
    bool check(int len) {
        memset(dp, 0, sizeof dp);
        dp[0][0][0] = 1;
        int mx = len / 2;
        rep(i, 0, len - 1) rep(s1, 0, mx) rep(s2, 0, mx)
            if (dp[i][s1][s2]) {
                if (s1 + a[i + 1] >= 0)
                    dp[i + 1][s1 + a[i + 1]][s2] = true;

                if (s2 + a[i + 1] >= 0)
                    dp[i + 1][s1][s2 + a[i + 1]] = true;

                if (s1 + a[i + 1] >= 0 && s2 + a[i + 1] >= 0)
                    dp[i + 1][s1 + a[i + 1]][s2 + a[i + 1]] = true;
            }
        return dp[len][0][0];
    }

    string base = "RGB";
    int dx[3] = {1, 1, 0};
    int dy[3] = {0, 1, 1};

    void trace(int len, int s1, int s2) {
        if (len == 0) return;
        rep(i, 0, 3) {
            int ns1 = s1 - dx[i] * a[len];
            int ns2 = s2 - dy[i] * a[len];
            if (dp[len - 1][ns1][ns2]) {
                trace(len - 1, ns1, ns2);
                cout << base[i];
                return;
            }
        }
    }

    void query() {
        string t;
        cin >> t;
        rep(i, 0, t.size() - 1)
            a[i + 1] = val(t[i]);
        if (check(t.size())) {
            trace(t.size(), 0, 0);
            cout << '\n';
        }
        else
            cout << "impossible\n";
    }

    void solve() {
        int q;
        cin >> q;
        while (q --) query();
    }
};

namespace P2 {
    const long long N = 1 << 15;
    bool dp[16][8][8];
    ll ans[20], a[20];
    bool check(int len) {
        memset(dp, 0, sizeof dp);
        dp[0][0][0] = 1;
        int mx = len / 2;
        rep(i, 0, len - 1) rep(s1, 0, mx) rep(s2, 0, mx)
            if (dp[i][s1][s2]) {
                if (s1 + a[i + 1] >= 0)
                    dp[i + 1][s1 + a[i + 1]][s2] = true;
                if (s2 + a[i + 1] >= 0)
                    dp[i + 1][s1][s2 + a[i + 1]] = true;
                if (s1 + a[i + 1] >= 0 && s2 + a[i + 1] >= 0)
                    dp[i + 1][s1 + a[i + 1]][s2 + a[i + 1]] = true;
            }
        return dp[len][0][0];
    }

    void solve() {
        rep(len, 1, 15) {
            rep(mask, 0, (1 << len) - 1) {
                rep(i, 0, len - 1) if (mask >> i & 1)
                    a[i + 1] = 1;
                else
                    a[i + 1] = -1;

                ans[len] += check(len);
            }
        }

        int q, n;
        cin >> q;
        while (q --) {
            cin >> n;
            cout << ans[n] << '\n';
        }
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int P;
    cin >> P;
    if (P == 1) P1 :: solve(); else P2 :: solve();

    return 0;
}

Compilation message

parentrises.cpp: In function 'void P1::query()':
parentrises.cpp:6:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i, n, m) for (ll i = (n); i <= (m); i ++)
      |                                         ^
parentrises.cpp:56:9: note: in expansion of macro 'rep'
   56 |         rep(i, 0, t.size() - 1)
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Runtime error 81 ms 1020 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 0 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Runtime error 81 ms 1020 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -