oj.uz

답안 #52813

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52813 2018-06-27T00:00:26 Z ainta(#1378) 괄호 문자열 (CEOI16_match) C++11
37 / 100
 2000 ms 708 KB 
#include<cstdio>
#include<algorithm>
#define N_ 101000
using namespace std;
char p[N_], st[N_], r[N_];
int n;
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;
		}
	}
	for (i = pv + 1; i <= n; i++) {
		if (top && st[top] == p[i])top--;
		else st[++top] = p[i];
	}
	if (!top)return true;
	return false;
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i, j;
	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++) {
		int b = i, e = n, mid, rr = i-1;
		while (b <= e) {
			mid = (b + e) >> 1;
			for (j = i; j <= mid; j++)r[j] = '(';
			if (Pos(mid))rr = mid, b = mid + 1;
			else e = mid - 1;
		}
		if (rr < i) {
			r[i] = ')';
		}
		else i = rr;
	}
	printf("%s\n", r + 1);
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:26: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 508 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 18 ms 508 KB Output is correct
5 Correct 16 ms 508 KB Output is correct
6 Correct 23 ms 508 KB Output is correct
7 Correct 98 ms 508 KB Output is correct

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 18 ms 508 KB Output is correct
5 Correct 16 ms 508 KB Output is correct
6 Correct 23 ms 508 KB Output is correct
7 Correct 98 ms 508 KB Output is correct
8 Correct 1448 ms 684 KB Output is correct
9 Correct 1354 ms 684 KB Output is correct
10 Correct 874 ms 704 KB Output is correct
11 Correct 633 ms 708 KB Output is correct
12 Execution timed out 2041 ms 708 KB Time limit exceeded
13 Halted 0 ms 0 KB -