oj.uz

Submission #608143

# Submission time Handle Problem Language Result Execution time Memory
608143 2022-07-27T05:36:35 Z chirathnirodha Match (CEOI16_match) C++17
100 / 100
 12 ms 11988 KB 
//Coded by Chirath Nirodha
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define P push
#define I insert
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
const ll mod=1e9+7;
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
string s;int last[100000][26];
string ans;
void rec(int l,int r){
	if(l>r)return;
	int x=s[l]-'a';
	if(last[r][x]<=l){
      	cout<<-1<<endl;
		exit(0);
	}
	ans[l]='(';
	ans[last[r][x]]=')';
	if(r-l==1)return;
	rec(l+1,last[r][x]-1);
	rec(last[r][x]+1,r);
}
void solve(){
    io();
	cin>>s;
	ans=s;
	int n=s.size();
	for(int i=0;i<n;i++){
		for(int j=0;j<26;j++){
			int x=s[i]-'a';
			if(x==j)last[i][j]=i;
			else if(i>0 && last[i-1][x]>0)last[i][j]=last[last[i-1][x]-1][j];
			else last[i][j]=-1;
		}
	}
	rec(0,n-1);
	cout<<ans<<endl;
}
int main(){
    io();
	solve();
	//int t;cin>>t;for(int i=0;i<t;i++)solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Correct 1 ms 1108 KB Output is correct
12 Correct 7 ms 7380 KB Output is correct
13 Correct 8 ms 8020 KB Output is correct
14 Correct 8 ms 8788 KB Output is correct
15 Correct 9 ms 10320 KB Output is correct
16 Correct 9 ms 10196 KB Output is correct
17 Correct 11 ms 10800 KB Output is correct
18 Correct 11 ms 10452 KB Output is correct
19 Correct 12 ms 11280 KB Output is correct
20 Correct 8 ms 7632 KB Output is correct
21 Correct 12 ms 11988 KB Output is correct