Submission #639686

#	Time	Username	Problem	Language	Result	Execution time	Memory
639686		BossBobster	parentrises (BOI18_parentrises)	C++17	72 / 100	53 ms	52088 KiB

parentrises

#include <iostream>
#include <string.h>
#include <random>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <array>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <valarray>
#include <memory>
#include <cassert>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<int, short> pish;
typedef pair<string, string> pss;
typedef pair<int, char> pic;
typedef pair<pii, int> piii;
typedef pair<double, double> pdd;
typedef pair<float, float> pff;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef pair<uint, uint> puint;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> plll;
typedef pair<pll, ld> plld;
typedef pair<int, ll> pil;
typedef pair<ull, ull> pull;
typedef pair<ld, ld> pld;
typedef complex<double> cd;
//#define max(n, m) ((n>m)?n:m)
//#define min(n, m) ((n<m)?n:m)
#define f first
#define s second
#define input() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define eps 1e-9
#define leni(x) sizeof(x)/sizeof(int)
//#define cin fin
//#define cout fout

const int mod = 1000000007;
int msum(int a, int b)
{
    a += b;
    if(a >= mod) a -= mod;
    return a;
}
int nums[1000010];
int pre;
char col[1000010];
int dp[310][210][210];
queue<int> cur;
int main()
{
    input();
    int p, t, n;
    string st;
    cin >> p >> t;
    if(p == 1)
    {
        while(t--)
        {
            cin >> st;
            n = (int)st.length();
            for(int i = 0; i < n; i ++)
                nums[i] = (st[i]=='(')?1:-1;
            pre = 0;
            //if prefix becomes < 0, remove two ')' from the beginning
            //if prefix ends up positive in the end, remove '(' from the end
            bool bad = false;
            while(cur.size())
                cur.pop();
            for(int i = 0; i < n; i ++)
                col[i] = 'G';
            for(int i = 0; i < n; i ++)
            {
                if(nums[i] == -1)
                {
                    cur.push(i);
                    pre --;
                    if(pre == -1)
                    {
                        if(cur.size() < 2) { bad = true; break; }
                        int a = cur.front(); cur.pop(); int b = cur.front(); cur.pop();
                        col[a] = 'R'; col[b] = 'B';
                        pre = 0;
                    }
                }
                else pre ++;
            }
            if(nums[n-1] == 1 || bad)
            {
                cout << "impossible\n";
                continue;
            }
            if(pre > 0)
            {
                int num = pre*2;
                char c = 'R';
                for(int i = n-1; i >= 0; i --)
                {
                    if(num == 0) break;
                    if(nums[i] == 1)
                    {
                        col[i] = c;
                        c = ((c=='R')?'B':'R');
                        num --;
                    }
                }
                if(num)
                {
                    cout << "impossible\n";
                    continue;
                }
            }
            pre = 0;
            for(int i = 0; i < n; i ++)
            {
                pre += nums[i]*((col[i]=='G')?2:1);
                if(pre < 0)
                {
                    bad = true;
                    break;
                }
            }
            if(pre > 0 || bad)
            {
                cout << "impossible\n";
                continue;
            }
            for(int i = 0; i < n; i ++)
                cout << col[i];
            cout << '\n';
        }
    }
    else
    {
        int lim = 300*2/3+5; //the limit for lower and upper bounds
        dp[0][0][0] = 1;
        for(int i = 0; i < 300; i ++)
            for(int j = 0; j < lim; j ++)
                for(int k = 0; k < lim; k ++)
                {
                    dp[i+1][j+1][k+2] = msum(dp[i+1][j+1][k+2], dp[i][j][k]);
                    if(k > 0) //we can do max(0, j-2) because we can set one ) to R and the other to B
                        dp[i+1][max(0, j-2)][k-1] = msum(dp[i+1][max(0, j-2)][k-1], dp[i][j][k]);
                }
        while(t--)
        {
            cin >> n;
            int ans = 0;
            for(int i = 0; i < lim; i ++)
                ans = msum(ans, dp[n][0][i]);
            cout << ans << '\n';
        }
    }
}

• 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: 0 / 28