Submission #74113

#	Time	Username	Problem	Language	Result	Execution time	Memory
74113		zscoder	parentrises (BOI18_parentrises)	C++17	100 / 100	52 ms	6984 KiB

parentrises

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int ans[1111111];

bool solve(string &s)
{
	int n=s.length();
	for(int i=0;i<n;i++) ans[i]=0;
	int ptr = 0;
	stack<int> S;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='(')
		{
			S.push(i);
		}
		else
		{
			if(!S.empty())
			{
				int u=S.top();
				ans[i]|=1; ans[u]|=1; S.pop();
			}
			else
			{
				while(ptr<i&&(s[ptr]!='('||ans[ptr]>=3)) ptr++;
				if(ptr>=i) return 0;
				ans[ptr]|=2; ans[i]|=2; 
			}
		}
	}
	ptr=n-1;
	for(int i=n-1;i>=0;i--)
	{
		if(s[i]==')'||ans[i]>0) continue;
		while(ptr>i&&(s[ptr]!=')'||ans[ptr]>=3)) ptr--;
		if(ptr<=i) return 0;
		ans[i]|=2; ans[ptr]|=2;
	}
	return 1;
}

bool valid(string &s)
{
	int cnt=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='(') cnt+=2;
		else cnt--;
		if(cnt<0) return false;
	}
	cnt=0;
	for(int i=int(s.length())-1;i>=0;i--)
	{
		if(s[i]==')') cnt+=2;
		else cnt--;
		if(cnt<0) return false;
	}
	return true;
}

const int MOD=1e9+7;

int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}

int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}

/*
const int C = 302;
int dp[303][606][906];

void gen(int n)
{
	freopen("parentrises-precomp.txt","w",stdout);
	memset(dp,0,sizeof(dp));
	cout<<"int ans[302]={0,";
	dp[0][0][C] = 1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<2*n;j++)
		{
			for(int k=-n;k<2*n;k++)
			{
				if(dp[i][j][k+C]>0)
				{
					//+ (
					int v=dp[i][j][k+C];
					//cerr<<i<<' '<<j<<' '<<k<<' '<<v<<'\n';
					dp[i+1][j+2][min(-1, -1+k)+C]=add(dp[i+1][j+2][min(-1, -1+k)+C],v);
					//+ )
					if(j>0) dp[i+1][j-1][min(2,2+k)+C] = add(dp[i+1][j-1][min(2,2+k)+C],v);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		int ans=0;
		for(int j=0;j<=2*n;j++)
		{
			for(int k=0;k<=2*n;k++)
			{
				ans=add(ans,dp[i][j][k+C]);
			}
		}
		cout<<ans;
		if(i+1<=n) cout<<",";
	}
	cout<<"};";
	cout<<'\n';
	return ;
}
*/
int res[302]={0,0,1,2,2,6,12,18,43,86,148,326,652,1194,2531,5062,9578,19884,39768,76680,157236,314472,613440,1248198,2496396,4906266,9932707,19865414,39237478,79165646,158331292,313801154,631634323,263268639,509707998,43257469,86514938,72895660,288290012,576580024,551498904,962513721,925027435,204521844,634307677,268615347,287719520,559111350,118222693,578936427,105459291,210918582,360752402,920849461,841698915,421349166,985137176,970274345,96196738,666703791,333407575,448451120,71192847,142385694,391328273,82210164,164420328,697441626,75399225,150798450,177655189,77725370,155450740,578770998,806452500,612904993,342317187,437431531,874863062,166780006,649351541,298703075,764861307,105948983,211897966,169754380,332500687,665001374,648783808,296688714,593377428,43060831,684124175,368248343,973819030,849070862,698141717,982308804,88186365,176372730,959772055,320975583,641951166,825442333,311190079,622380158,765671696,14446067,28892134,262223145,966556598,933113189,520941027,287565710,575131420,666019185,263936054,527872108,39283492,877846547,755693087,433079969,737806887,475613767,203965075,701508060,403016113,922600280,277710517,555421034,408729101,377397802,754795604,250532053,528340400,56680793,124734442,232656836,465313672,714603167,631625056,263250105,52648990,389536240,779072480,641256163,302398795,604797590,697370162,632833340,265666673,626109777,298187773,596375546,406717000,515830626,31661245,524137426,667633864,335267721,338047842,390892123,781784246,93415445,65330389,130660778,151215664,822766849,645533691,833650616,380489231,760978462,54775313,491923347,983846694,322809267,940997512,881995017,596258099,507985218,15970429,557503950,859869218,719738429,474482700,767988978,535977949,635491203,387005395,774010790,702061186,253594815,507189630,31838831,822372294,644744581,231777149,215914547,431829094,482869402,576014681,152029355,369499245,244741222,489482444,95772722,952809165,905618323,304323137,304632041,609264082,102336119,335070266,670140532,858231094,960619772,921239537,859847032,56893721,113787442,360033502,982628521,965257035,849451750,439416129,878832258,991939394,464496385,928992770,267785589,802816545,605633083,763528731,474974661,949949322,864267253,946087508,892175009,476000768,273171027,546342054,550581443,469352643,938705286,624000951,673806443,347612879,434823692,233016716,466033432,103642988,440059594,880119188,788176043,40656596,81313192,286602731,202636014,405272028,733717711,472596468,945192936,553096598,892385168,784770329,912447619,707646096,415292185,526477156,861291715,722583423,111861393,588150125,176300243,301383510,244253166,488506332,629844702,421869639,843739278,290375226,384946885,769893770,95673275,473895679,947791358,891751001,164209639,328419278,62075416,175112411,350224822,934621064,806088783,612177559,897003764,948394637,896789267,953901352,418921686,837843372,499200486};

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	//gen(301); return 0;
	/*
	int n; cin>>n;
	for(int i=0;i<(1<<n);i++)
	{
		string s;
		for(int j=0;j<n;j++)
		{
			if(i&(1<<j)) s+='(';
			else s+=')';
		}
		bool tmp = solve(s);
		bool tmp2 = valid(s);
		if(tmp!=tmp2)
		{
			cout<<s<<'\n'; return 0;
		}
	}
	return 0;
	*/
	int type; cin>>type;
	int t; cin>>t;
	while(t--)
	{
		if(type==1)
		{
			string s; cin>>s; 
			bool tmp = solve(s);
			if(!tmp) 
			{
				cout<<"impossible\n"; 
				continue;
			}
			for(int i=0;i<s.length();i++)
			{
				if(ans[i]==1) cout<<"B";
				else if(ans[i]==2) cout<<"R";
				else cout<<"G";
			}
			cout<<'\n';		
		}
		else
		{
			int n; cin>>n;
			cout<<res[n]<<'\n';
		}
	}
}	

Compilation message (stderr)

parentrises.cpp: In function 'bool valid(std::__cxx11::string&)':
parentrises.cpp:62:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.length();i++)
              ~^~~~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:176:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<s.length();i++)
                ~^~~~~~~~~~~

• 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