oj.uz

Submission #61879

# Submission time Handle Problem Language Result Execution time Memory
61879 2018-07-27T04:02:33 Z ainta(#1792) parentrises (BOI18_parentrises) C++11
0 / 100
 3 ms 500 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");
		}
	}
}
void Solve2() {
}
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 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 'int main()':
parentrises.cpp:90: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 1 ms 484 KB Output is correct
3 Incorrect 3 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 3 ms 484 KB Output is correct
2 Incorrect 2 ms 500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 500 KB Unexpected end of file - int32 expected

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 500 KB Unexpected end of file - int32 expected

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 500 KB Unexpected end of file - int32 expected