Submission #680658

#	Time	Username	Problem	Language	Result	Execution time	Memory
680658		Duy_e	parentrises (BOI18_parentrises)	C++14	22 / 100	98 ms	1028 KiB

parentrises

#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][15][15];
    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 (stderr)

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 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 6
• Subtask 4: 0 / 28
• Subtask 5: 6 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28