oj.uz

Submission #52813

# Submission time Handle Problem Language Result Execution time Memory
52813 2018-06-27T00:00:26 Z ainta(#1378) Match (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -