oj.uz

Submission #749651

# Submission time Handle Problem Language Result Execution time Memory
749651 2023-05-28T10:47:05 Z 박상훈(#9965) Match (CEOI16_match) C++17
10 / 100
 2 ms 1236 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, dp[100100][33], sp[100100][33], L[100100], R[100100];
char a[100100], ans[100100];

bool ok(int s, int e, vector<int> st){
	if (e-s < -1) return 0;

	for (int i=s;i<=e;i++){
		if (!st.empty() && st.back()==a[i]) st.pop_back();
		else st.push_back(a[i]);
	}

	return st.empty();
}

void init(){
	if (!ok(1, n, vector<int>())){
		printf("-1\n");
		exit(0);
	}

	fill(L+1, L+n+1, -1);
	fill(R+1, R+n+1, -1);

	for (int i=0;i<=n;i++) fill(dp[i], dp[i]+26, -1);
	for (int i=1;i<=n;i++){
		L[i] = dp[i-1][a[i]-'a'];

		if (L[i]==-1) R[i] = -1;
		else R[L[i]] = i;

		dp[i][a[i]-'a'] = i;

		for (int j=0;j<26;j++){
			if (j!=a[i]-'a' && L[i]!=-1){
				dp[i][j] = dp[L[i]-1][j];
			}
		} 
	}

	for (int i=1;i<=n;i++){
		sp[i][0] = R[i];
	}
	for (int j=1;j<20;j++){
		for (int i=1;i<=n;i++){
			if (sp[i][j-1]!=-1){
				sp[i][j] = sp[sp[i][j-1] + 1][j-1];
			}
			else sp[i][j] = -1;
		}
		
	}

	// printf(" %d\n", sp[4][0]);
}

bool valid(int l, int r){
	if (r-l+1 < 0) return 0;

	for (int j=19;j>=0;j--) if (l<=n && sp[l][j]!=-1 && sp[l][j] <= r){
		l = sp[l][j] + 1;
	}

	return r-l+1 == 0;
}

int main(){
	scanf("%s", a+1);
	n = strlen(a+1);

	init();

	vector<int> st;
	vector<pair<int, int>> st2;
	for (int i=1,j=n;i<=n;i++){
		st.push_back(a[i]);

		int nj = dp[j][a[i]-'a'];
		// printf("\ni = a%d -> nj = %d\n", i, nj);
		if (valid(i+1, nj-1)){
			// printf("push ok\n");
			ans[i] = '(';
			st2.emplace_back(a[nj], nj);

			j = nj-1;
		}

		else{
			// printf("pop\n");
			ans[i] = ')';

			st.pop_back();
			assert(!st.empty() && st.back()==a[i]);

			st.pop_back();
			st2.pop_back();
			j = st2.empty()?n:(st2.back().second-1);
		}

		// auto st20 = st2;
		// while(j>0){
		// 	if (st.size()==st2.size()+1 && a[j]==a[i]){
		// 		st2.emplace_back(a[j], j);
		// 		j--;
		// 		break;
		// 	}

		// 	else if (st.size()==st2.size()+1 || st2.back().first!=a[j]){
		// 		st2.emplace_back(a[j], j);
		// 		j--;
		// 	}
		// 	else{
		// 		st2.pop_back();
		// 		j--;
		// 	}
		// }

		// if (!ok(i+1, j, vector<int>())){
		// 	st.pop_back();
		// 	st2 = st20;
		// 	assert(!st.empty() && st.back()==a[i]);

		// 	st.pop_back();
		// 	st2.pop_back();
		// 	j = st2.empty()?n:(st2.back().second-1);

		// 	ans[i] = ')';
		// }

		// else ans[i] = '(';

		// printf("i = %d -> j = %d\n", i, j);
		// for (auto &x:st) printf("%d ", x-'a'+1);
		// printf("\n");
		// for (auto &[x, y]:st2) printf("(%d, %d) ", x-'a'+1, y);
		// printf("\n");


	}
	ans[n+1] = 0;

	printf("%s\n", ans+1);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Runtime error 2 ms 1236 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Runtime error 2 ms 1236 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -