oj.uz

Submission #61752

# Submission time Handle Problem Language Result Execution time Memory
61752 2018-07-26T14:20:00 Z Benq parentrises (BOI18_parentrises) C++11
22 / 100
 327 ms 107024 KB 
#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][301][301];

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

void gen() {
    dp[0][0][0] = 1;
    F0R(i,300) F0R(j,301) F0R(k,301) {
        if (j+2 < 301 && 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 += 'R';
            else cur.f ++, res += 'B';
        } 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,301) 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 106864 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 106864 KB Output is correct
2 Correct 293 ms 106940 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 106864 KB Output is correct
2 Correct 293 ms 106940 KB Output is correct
3 Incorrect 317 ms 107024 KB Output isn't correct