oj.uz

Submission #698520

# Submission time Handle Problem Language Result Execution time Memory
698520 2023-02-13T17:00:13 Z dattranxxx Match (CEOI16_match) C++11
10 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 5;
char ans[N];
string s;
vector<int> idx[26];

int n;

void solve(int l, int r) {
  if (l > r) return;
  int c = s[l] - 'a';
  int m = upper_bound(idx[c].begin(), idx[c].end(), r) - idx[c].begin() - 1;
  
  if (m == -1 || idx[c][m] <= l) {
    cout << -1;
    exit(0);
  }
  m = idx[c][m];
  
  ans[l] = '(';
  ans[m] = ')';
  
  solve(l + 1, m - 1);
  solve(m + 1, r);
  
}

int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  cin >> s; 
  n = s.size();
  s = ' ' + s;
  for (int i = 1; i <= n; ++i) {
    idx[s[i] - 'a'].emplace_back(i);
  }
  
  solve(1, n);
  
  for (int i = 1; i <= n; ++i) {
    cout << ans[i];
  }
  
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -