oj.uz

Submission #134175

# Submission time Handle Problem Language Result Execution time Memory
134175 2019-07-22T07:50:16 Z 이온조(#3229) Match (CEOI16_match) C++14
0 / 100
 114 ms 127224 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
char S[100009];
int ans[100009], bck[100009];
set<int> st[27][100009];
bool fin[100009];

int main() {
	scanf("%s", S+1);
	N = strlen(S+1);
	vector<int> T = {0}; S[0] = '_';
	for(int i=1; i<=N; i++) {
		if(S[T.back()] == S[i]) {
			ans[i] = T.back();
			T.pop_back();
			bck[i] = T.back();
			st[S[i] - 'a'][bck[i]].insert(i);
		}
		else {
			ans[i] = i;
			fin[i] = 1;
			T.push_back(i);
		}
	}
	if(T.back()) return !printf("-1");
	T = {N+1};
	for(int i=1; i<=N; i++) {
		if(fin[i]) continue;
		while(T.back() < i) T.pop_back();
		int rm = *prev(st[S[i] - 'a'][bck[i]].lower_bound(T.back()));
		if(rm == i) continue;
		fin[ans[rm]] = fin[rm] = 1;
		ans[ans[rm]] = -1; ans[rm] = -1;
		ans[i] = i;
		T.push_back(rm);
	}
	for(int i=1; i<=N; i++) {
		if(ans[i] == i) printf("(");
		else printf(")");
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 127224 KB Output is correct
2 Incorrect 114 ms 127196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 127224 KB Output is correct
2 Incorrect 114 ms 127196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 127224 KB Output is correct
2 Incorrect 114 ms 127196 KB Output isn't correct
3 Halted 0 ms 0 KB -