oj.uz

Submission #52814

# Submission time Handle Problem Language Result Execution time Memory
52814 2018-06-27T00:30:26 Z ainta(#1378) Match (CEOI16_match) C++11
10 / 100
 3 ms 520 KB 
#include<cstdio>
#include<algorithm>
#define N_ 101000
using namespace std;
char p[N_], st[N_], r[N_];
int n, st2[N_];
bool OK(int b, int e) {
	int i, t = 0;
	for (i = b; i <= e; i++) {
		if (t && st2[t] == p[i])t--;
		else st2[++t] = p[i];
	}
	return t == 0;
}
bool Pos(int pv) {
	int i, top = 0;
	for (i = 1; i <= pv; i++) {
		if (r[i] == '(')st[++top] = p[i];
		else {
			if (top && st[top] == p[i])top--;
			else return false;
		}
	}
	int pt = 1, ed = n;
	for (i = n; i > pv; i--) {
		if (pt <= top && st[pt] == p[i]) {
			if (!OK(i + 1, ed))return false;
			pt++;
			ed = i - 1;
		}
	}
	if (pt != top + 1)return false;
	if (!OK(pv + 1, ed))return false;
	return true;
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i;
	scanf("%s", p + 1);
	for (i = 1; p[i]; i++);
	n = i - 1;
	if (!Pos(0)) {
		puts("-1");
		return 0;
	}
	for (i = 1; i <= n; i++) {
		r[i] = '(';
		if (!Pos(i)) {
			r[i] = ')';
		}
	}
	printf("%s\n", r + 1);
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", p + 1);
  ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 520 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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