Submission #61755

#	Time	Username	Problem	Language	Result	Execution time	Memory
61755		Benq	parentrises (BOI18_parentrises)	C++11	100 / 100	750 ms	213208 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 = 1000001;
 
int P,T,dp[301][601][301];
 
void AD(int& a, int b) { a = (a+b)%MOD; }
 
void gen() {
    dp[0][0][0] = 1;
    F0R(i,300) F0R(j,601) F0R(k,301) {
        if (j+2 < 601 && k+1 < 301) AD(dp[i+1][j+2][k+1],dp[i][j][k]);
        if (j-1 >= 0) AD(dp[i+1][j-1][max(k-2,0)],dp[i][j][k]);
    }
}
 
int num[MX];
 
string solve1(string s) {
    vi a, b;
    F0R(i,sz(s)) {
        if (s[i] == '(') a.pb(i);
        else b.pb(i);
    }
    int dif = sz(a)-sz(b);
    int i0 = max(-dif,0), i1 = max(dif,0);
    while (i0 < sz(a) && sz(b)-1-i1 >= 0 && a[i0] < b[sz(b)-1-i1]) i0 ++, i1 ++;
    
    if (i0 > sz(a) || i1 > sz(b)) return "impossible";
    
    for (int i: a) num[i] = 1;
    F0R(i,i0) num[a[i]] = 2;
    for (int i: b) num[i] = -1;
    F0R(i,i1) num[b[sz(b)-1-i]] = -2;
    
    /*cout << s << "\n";
    F0R(i,sz(s)) cout << num[i] << " ";
    cout << "\n";*/
    
    pi cur = {0,0};
    string res;
    F0R(i,sz(s)) {
        if (num[i] == 2) {
            cur.f ++, cur.s ++;
            res += 'G';
        } else if (num[i] == -2) {
            cur.f --, cur.s --;
            res += 'G';
            if (cur.s < 0) return "impossible";
        } else if (num[i] == 1) {
            if (cur.f > cur.s) cur.s ++, res += 'B';
            else cur.f ++, res += 'R';
        } else {
            if (cur.f > cur.s) cur.f --, res += 'R';
            else cur.s --, res += 'B';
            if (cur.s < 0) return "impossible";
        }
    }
    if (cur != mp(0,0)) return "impossible";
    return res;
}
 
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;
            int ans = 0;
            F0R(i,601) AD(ans,dp[x][i][0]);
            cout << ans << "\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: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28