oj.uz

Submission #698539

# Submission time Handle Problem Language Result Execution time Memory
698539 2023-02-13T17:47:53 Z dattranxxx Match (CEOI16_match) C++11
37 / 100
 2000 ms 980 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 5;
string s;
int n;

char ans[N];

int good(stack<char> st, int i) {
  for (; i <= n; ++i) {
    if (st.empty() || st.top() != s[i]) {
      st.push(s[i]);
    } else {
      st.pop();
    }
  }
  return st.empty();
}

void task1() {
  
  stack<char> st;
  for (int i = 1; i <= n; ++i) {
    if (st.empty() || st.top() != s[i]) {
      st.push(s[i]);
      ans[i] = '(';
    } else {
      
      st.push(s[i]);
      ans[i] = '(';
      if (good(st, i + 1)) continue;
      st.pop();
      ans[i] = ')';
      st.pop();
      
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << ans[i];
  }
  exit(0);
  
}

int last[N][26];

void solve(int l, int r) {
  if (l > r) return;
  int m = last[r][s[l] - 'a'];
  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;
  
  if (!good(stack<char>(), 1)) {
    cout << -1;
    return 0;
  }
  
  if (n <= 2000) task1();
  
  // last[i][c] = max j sao cho [j + 1..i] tm va s[j] = c
  
  for (int i = 1; i <= n; ++i) {
    last[i][s[i] - 'a'] = i;
    
    for (int j = i - 1; j;) {
      if (!last[j][s[i] - 'a']) break;

      
      if (!last[i][s[last[j][s[i] - 'a'] - 1] - 'a']) {
        
        last[i][s[last[j][s[i] - 'a'] - 1] - 'a'] = last[j][s[i] - 'a'] - 1;
      }
      
      j = last[j][s[i] - 'a'] - 1;
    }
    
  }
  
  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 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Execution timed out 2083 ms 980 KB Time limit exceeded
9 Halted 0 ms 0 KB -