oj.uz

Submission #610224

# Submission time Handle Problem Language Result Execution time Memory
610224 2022-07-28T05:53:32 Z kshitij_sodani Match (CEOI16_match) C++14
100 / 100
 38 ms 4948 KB 
#include <bits/stdc++.h>
#define a first
#define b second
#define pb push_back
using namespace std;
typedef long long llo;

vector<int> pre[100001];
int it[100001];
int ans[100001];
int ind2[100001];
int co[100001];
int co2[100001];
int par[100001][20];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string s;

	cin>>s;
	int n=s.size();
	for(int i=0;i<s.size();i++){
		pre[s[i]-'a'].pb(i);
		it[i]=s[i]-'a';
	}
	for(int i=0;i<n;i++){
		ind2[i]=-1;
		if(i>0){
			int cur=i-1;
			while(cur>=0){

				if(it[cur]==it[i]){
					ind2[i]=cur;
					break;
				}
				
				if(ind2[cur]==-1){
					break;
				}
				cur=ind2[cur]-1;
			}
		}
	}


	
	vector<int> ss;
	vector<int> xx;
	for(int i=0;i<n;i++){
		//cout<<i<<":"<<endl;
		if(ss.size()){
			if(ss.back()==it[i]){
				vector<int> tt;
				//tt.pb(it[i]);
				int st=0;
				int cur=xx.back()-1;
				while(cur>i){
					if(it[cur]==it[i] and st==0){
						xx.pb(cur);
						st=1;
						cur--;
						continue;
					}
					cur=ind2[cur]-1;
				}

				if(cur!=i and st==1){
					st=0;
					xx.pop_back();
				}
				//cout<<i<<":"<<st<<","<<cur<<":"<<xx.back()<<endl;
				if(st==1){
					ss.pb(it[i]);
					ans[i]=1;
				}
				else{
					ss.pop_back();
					xx.pop_back();
					ans[i]=-1;
				}
				//cout<<i<<":"<<ans[i]<<","<<endl;
				continue;
			}
		}
		int cur=n-1;
		if(xx.size()){
			cur=xx.back()-1;
		}
		int st=0;
		while(cur>i){
			if(it[cur]==it[i]){
				st=1;
				xx.pb(cur);
				break;
			}
			else{
				cur=ind2[cur]-1;

			}
		}

		if(st==0){
			cout<<-1<<endl;
			return 0;
		}
		ss.pb(it[i]);
		ans[i]=1;
	}
	if(ss.size()!=0){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=0;i<n;i++){
		if(ans[i]==1){
			cout<<'(';
		}
		else{
			cout<<')';
		}
	}
	cout<<endl;










	return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2900 KB Output is correct
12 Correct 5 ms 4052 KB Output is correct
13 Correct 5 ms 4308 KB Output is correct
14 Correct 5 ms 4308 KB Output is correct
15 Correct 34 ms 4424 KB Output is correct
16 Correct 38 ms 4420 KB Output is correct
17 Correct 7 ms 4692 KB Output is correct
18 Correct 14 ms 4504 KB Output is correct
19 Correct 9 ms 4948 KB Output is correct
20 Correct 7 ms 4180 KB Output is correct
21 Correct 10 ms 4948 KB Output is correct