Submission #61943

#	Time	Username	Problem	Language	Result	Execution time	Memory
61943		khsoo01	parentrises (BOI18_parentrises)	C++11	100 / 100	131 ms	55312 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;

const int N = 2000005;

int n;
char a[N], b[N];

void solve1 () {
	scanf("%s",a+1);
	n = strlen(a+1);
	queue<int> X, Y, Q;
	int A = 0, B = 0, C = 0, D = 0;
	for(int i=1;i<=n;i++) {
		if(a[i] == '(') {
			if(D < C) {
				D++;
				B++;
				b[i] = 'R';
				Y.push(i);
			}
			else {
				C++;
				A++;
				b[i] = 'B';
				X.push(i);
			}
		}
		else {
			A--;
			B--;
			b[i] = 'G';
			Q.push(i);
		}
		while(A < 0 && !Y.empty()) {
			int T = Y.front();
			Y.pop();
			b[T] = 'G';
			A++;
		}
		while(B < 0 && !X.empty()) {
			int T = X.front();
			X.pop();
			b[T] = 'G';
			B++;
		}
		while(A < 0 && !Q.empty()) {
			int T = Q.front();
			Q.pop();
			b[T] = 'R';
			A++;
		}
		while(B < 0 && !Q.empty()) {
			int T = Q.front();
			Q.pop();
			b[T] = 'B';
			B++;
		}
		if(A < 0 || B < 0) {
			puts("impossible");
			return;
		}
	}
	if(A > 0 || B > 0) {
		puts("impossible");
		return;
	}
	b[n+1] = 0;
	printf("%s\n",b+1);
}

const int M = 301, mod = 1e9+7;

int dt[M][M][M];

void calc () {
	dt[0][0][0] = 1;
	for(int i=1;i<M;i++) for(int j=0;j<i;j++) for(int k=0;k<i;k++) {
		if(k >= 2) {
			dt[i][j+1][k-2] = (dt[i][j+1][k-2] + dt[i-1][j][k]) % mod;
		}
		else if(j+k >= 1) {
			dt[i][j+k-1][0] = (dt[i][j+k-1][0] + dt[i-1][j][k]) % mod;
		}
		dt[i][j+1][k+1] = (dt[i][j+1][k+1] + dt[i-1][j][k]) % mod;
	}
}

void solve2() {
	int T, R = 0;
	scanf("%d",&T);
	for(int i=0;i<M;i++) {
		R = (R + dt[T][i][0]) % mod;
	}
	printf("%d\n",R);
}

int main()
{
	int typ, tc;
	scanf("%d%d",&typ,&tc);
	if(typ == 2) calc();
	while(tc--) {
		if(typ == 1) solve1();
		else solve2();
	}
}

Compilation message (stderr)

parentrises.cpp: In function 'void solve1()':
parentrises.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",a+1);
  ~~~~~^~~~~~~~~~
parentrises.cpp: In function 'void solve2()':
parentrises.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&T);
  ~~~~~^~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&typ,&tc);
  ~~~~~^~~~~~~~~~~~~~~~~

• 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