oj.uz

답안 #609838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609838 2022-07-28T00:49:42 Z GusterGoose27 괄호 문자열 (CEOI16_match) C++11
0 / 100
 1 ms 468 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";
		assert(false);
	}
	else {
		for (int i = 0; i < n; i++) {
			if (seq[i]) cout << ")";
			else cout << "(";
		}
		cout << "\n";
	}
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -