Submission #61497

#	Time	Username	Problem	Language	Result	Execution time	Memory
61497		Benq	parentrises (BOI18_parentrises)	C++11	0 / 100	186 ms	55128 KiB

parentrises

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int P, T, dp[301][301][301], ans[301];

void AD(int& a, int b) { a = (a+b)%MOD; }

void gen() {
    dp[0][0][0] = 1;
    F0R(i,300) {
        F0R(j,i+1) F0R(k,i+1) {
            AD(dp[i+1][j+1][k+1],dp[i][j][k]);
            AD(dp[i+1][j][k+1],dp[i][j][k]);
            AD(dp[i+1][j+1][k],dp[i][j][k]);
            if (j) {
                AD(dp[i+1][j-1][k],dp[i][j][k]);
                if (k) AD(dp[i+1][j-1][k-1],dp[i][j][k]);
            }
            if (k) AD(dp[i+1][j][k-1],dp[i][j][k]);
        }
        ans[i+1] = dp[i+1][0][0];
        cout << "HI " << i+1 << " " << ans[i+1] << "\n";
    }
}

int done[1000001];

vi get(string s) {
    queue<int> a;
    vi ret;
    F0R(i,sz(s)) {
        if (s[i] == '(') a.push(i);
        else if (sz(a)) {
            ret.pb(a.front()); a.pop();
            ret.pb(i);
        }
    }
    return ret;
}

string trans(string s) {
    reverse(all(s));
    for (char& c: s) if (c == '(') c = ')';
    else c = '(';
    return s;
}

string solve1(string s) {
    F0R(i,sz(s)) done[i] = 0;
    vi ret = get(s);
    for (int i: ret) {
        done[i] ^= 1;
        // cout << i << " ";
    }
    // cout << "\n";
    
    // cout << s << " " << trans(s) << "\n";
    vi RET = get(trans(s));
    for (int i: RET) done[sz(s)-1-i] ^= 2;
    
    string ans;
    F0R(i,sz(s)) {
        if (done[i] == 0) return "impossible";
        if (done[i] == 1) ans += 'R';
        else if (done[i] == 2) ans += 'B';
        else ans += 'G';
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> P >> T;
    if (P == 1) {
        F0R(i,T) {
            string s; cin >> s;
            cout << solve1(s) << "\n";
        }
    } else {
        gen();
        F0R(i,T) {
            int x; cin >> x;
            cout << ans[x] << "\n";
        }
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 6
• Subtask 4: 0 / 28
• Subtask 5: 0 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28