oj.uz

Submission #202300

# Submission time Handle Problem Language Result Execution time Memory
202300 2020-02-15T07:54:33 Z quocnguyen1012 Match (CEOI16_match) C++14
100 / 100
 21 ms 12148 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int N;
int last[maxn][26];
string str;
char res[maxn];

void match(int l, int r)
{
  if (l > r) return;
  if (l % 2 == r % 2){
    cout << -1;
    exit(0);
  }
  int mid = last[r][str[l] - 'a'];
  res[l] = '('; res[mid] = ')';
  match(l + 1, mid - 1);
  match(mid + 1, r);
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> str; N = str.size();
  str = " " + str;
  for (int i = 0; i < 26; ++i){
    last[0][i] = 1;
  }
  for (int i = 1; i <= N; ++i){
    for (int j = 0; j < 26; ++j){
      if (str[i] - 'a' == j){
        last[i][j] = i;
      }
      else{
        last[i][j] = last[last[i - 1][str[i] - 'a'] - 1][j];
      }
    }
  }
  match(1, N);
  for (int i = 1; i <= N; ++i){
    cout << res[i];
  }
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
match.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 6 ms 1144 KB Output is correct
9 Correct 6 ms 1144 KB Output is correct
10 Correct 6 ms 1144 KB Output is correct
11 Correct 6 ms 1272 KB Output is correct
12 Correct 14 ms 7544 KB Output is correct
13 Correct 18 ms 8232 KB Output is correct
14 Correct 16 ms 8948 KB Output is correct
15 Correct 17 ms 10356 KB Output is correct
16 Correct 17 ms 10356 KB Output is correct
17 Correct 20 ms 10996 KB Output is correct
18 Correct 18 ms 10612 KB Output is correct
19 Correct 21 ms 11380 KB Output is correct
20 Correct 14 ms 7672 KB Output is correct
21 Correct 21 ms 12148 KB Output is correct