oj.uz

Submission #604440

# Submission time Handle Problem Language Result Execution time Memory
604440 2022-07-25T06:32:35 Z MetalPower Match (CEOI16_match) C++14
10 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX = 2e3 + 10;

int N, ans[MX]; string s;
vector<int> arr[MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> s;
	N = s.length();

	for(int i = 0; i < N; i++)
		arr[s[i] - 'a'].push_back(i);
	
	bool f = true;
	for(int i = 0; i < 26; i++){
		if(arr[i].size() % 2 == 1){
			f = false;
			break;
		}
	}

	if(!f){
		cout << -1 << '\n';
		return 0;
	}

	vector<int> stk; // close brackets
	stk.push_back(N);

	for(int i = 0; i < N; i++){
		int ch = s[i] - 'a';
		if(ans[i] == 0){
			int fn = stk.back(), idx = lower_bound(arr[ch].begin(), arr[ch].end(), fn) - arr[ch].begin();
			if(idx > 0 && arr[ch][idx - 1] > i){
				ans[arr[ch][idx - 1]] = -1;
				ans[i] = 1;
				stk.push_back(arr[ch][idx - 1]);
			}else{
				f = false;
				break;
			}
		}else{
			stk.pop_back();
		}
	}

	if(!f){
		cout << -1 << '\n';
		return 0;
	}

	for(int i = 0; i < N; i++){
		if(ans[i] == 1) cout << '(';
		else cout << ')';
	}
	cout << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -