oj.uz

답안 #609833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609833 2022-07-28T00:46:29 Z GusterGoose27 괄호 문자열 (CEOI16_match) C++11
10 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
int n;
string s;
int nextocc[MAXN+1][20];
map<char, int> occ;
bool failflag = 0;
bool seq[MAXN]; // 0 open, 1 close

void make(int l, int r) {
	if (r < l) return;
	if ((r-l) % 2 == 0) {
		failflag = 1;
		return;
	}
	int pos = l;
	for (int i = 19; i >= 0; i--) {
		if (nextocc[pos][i] <= r) pos = nextocc[pos][i];
	}
	if (pos == l) {
		failflag = 1;
		return;
	}
	seq[l] = 0;
	seq[pos] = 1;
	make(l+1, pos-1);
	make(pos+1, r);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; i++) {
		char c = s[i];
		if (occ.find(c) != occ.end()) {
			nextocc[occ[c]][0] = i;
		}
		occ[c] = i;
	}
	for (auto p: occ) nextocc[p.second][0] = n;
	occ.clear();
	nextocc[n][0] = n;
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i <= n; i++) nextocc[i][j] = nextocc[nextocc[i][j-1]][j-1];
	}
	make(0, n-1);
	if (failflag) cout << "-1\n";
	else {
		for (int i = 0; i < n; i++) {
			if (seq[i]) cout << ")";
			else cout << "(";
		}
		cout << "\n";
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -