oj.uz

Submission #61885

# Submission time Handle Problem Language Result Execution time Memory
61885 2018-07-27T04:22:46 Z ainta(#1792) parentrises (BOI18_parentrises) C++11
22 / 100
 1000 ms 1264 KB 
#include<cstdio>
#include<algorithm>
#include<queue>
#define N_ 1010000
using namespace std;
char p[N_];
int n, S[N_], v[N_];
void Do1() {
	int i;
	S[0] = 0;
	for (i = 0; i < n; i++) {
		if (p[i] == '(')S[i + 1] = S[i] + 1;
		else S[i + 1] = S[i] - 1;
	}
	int Mn = 0;
	for (i = 1; i <= n; i++) {
		if (Mn > S[i]) {
			Mn = S[i];
			v[i-1] = 1;
		}
	}
	int t = S[n] - Mn;
	for (i = n - 1; i >= 0 && t; i--) {
		if (p[i] == '(') {
			t--;
			v[i] = 1;
		}
	}
}
bool Do2() {
	int i;
	queue<int>Q;
	int s = 0;
	for (i = 0; i < n; i++) {
		if (p[i] == '(')s++;
		if (p[i] == ')')s--;
		if (!v[i] && p[i] == ')') {
			Q.push(i);
		}
		if (s < 0) {
			if (Q.empty())return false;
			v[Q.front()] = 2;
			Q.pop();
			s++;
		}
	}
	for (i = n - 1; i >= 0 && s; i--) {
		if (!v[i] && p[i] == '(') {
			s--;
			v[i] = 2;
		}
	}
	int ss = 0;
	for (i = 0; i < n; i++) {
		if (v[i] != 2) {
			if (p[i] == '(')ss++;
			else ss--;
		}
		if (ss < 0)return false;
	}
	if (ss)return false;
	return true;
}
void Solve1() {
	int TC, i;
	scanf("%d", &TC);
	while (TC--) {
		scanf("%s", p);
		for (i = 0; p[i]; i++)v[i] = 0;
		n = i;
		Do1();
		if (Do2()) {
			for (i = 0; i < n; i++) {
				if (v[i] == 1)printf("R");
				else if (v[i] == 2)printf("B");
				else printf("G");
			}
			printf("\n");
		}
		else {
			puts("impossible");
		}
	}
}
int Mod = 1000000007, D[310][610];

int Calc2(int n, int M) {
	int i, j;
	for (i = 0; i <= n; i++) for (j = 0; j <= n + n; j++) D[i][j] = 0;
	D[0][n] = 1;
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= n + n; j++) {
			int t = j - n;
			if ((-t) * 3 > i)D[i][j] = 0;
			t = (j - n) - M;
			if ((-t) * 3 > (n - i))D[i][j] = 0;
			if (!D[i][j])continue;
			D[i + 1][j + 1] = (D[i + 1][j + 1] + D[i][j]) % Mod;
			D[i + 1][j - 1] = (D[i + 1][j - 1] + D[i][j]) % Mod;
		}
	}
	return D[n][n + M];
}

int Calc(int n) {

	int res = 0;
	int t = n / 3, i;
	for (i = -t; i <= t; i++) {
		res = (res + Calc2(n, i)) % Mod;
	}
	return res;
}
void Solve2() {
	int i, TC, n;
	scanf("%d", &TC);
	while (TC--) {
		scanf("%d", &n);
		printf("%d\n", Calc(n));
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int ck;
	scanf("%d", &ck);
	if (ck == 1) {
		Solve1();
	}
	else {
		Solve2();
	}
}

Compilation message

parentrises.cpp: In function 'void Solve2()':
parentrises.cpp:115:6: warning: unused variable 'i' [-Wunused-variable]
  int i, TC, n;
      ^
parentrises.cpp: In function 'void Solve1()':
parentrises.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &TC);
  ~~~~~^~~~~~~~~~~
parentrises.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", p);
   ~~~~~^~~~~~~~~
parentrises.cpp: In function 'void Solve2()':
parentrises.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &TC);
  ~~~~~^~~~~~~~~~~
parentrises.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &ck);
  ~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Incorrect 3 ms 536 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 492 KB Output is correct
2 Incorrect 3 ms 536 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 492 KB Output is correct
2 Incorrect 3 ms 536 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 2 ms 568 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 4 ms 568 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 4 ms 568 KB Output is correct
3 Execution timed out 1082 ms 1264 KB Time limit exceeded