oj.uz

Submission #48111

# Submission time Handle Problem Language Result Execution time Memory
48111 2018-05-10T05:23:29 Z Extazy Match (CEOI16_match) C++17
100 / 100
 9 ms 1576 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 100007;

int n;
char a[N],ans[N];
int pos[N];

bool can(int l, int r) {
  stack < char > s;
  int i;

  for(i=l;i<=r;i++) {
    if(!s.empty() && s.top()==a[i]) s.pop();
    else s.push(a[i]);
  }

  return s.empty();
}

void solve(int l, int r) {
  if(l>r) return;
  if(a[l]==a[r]) {
    ans[l]='(';
    ans[r]=')';
    solve(l+1,r-1);
    return;
  }
  
  int where=pos[r];

  while(a[l]!=a[where-1]) {
    where=pos[where-1];
  }

  assert(where>l);
  
  if(l<where-1) {
    ans[l]='(';
    ans[where-1]=')';
  }

  solve(l+1,where-2);
  solve(where,r);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i,where;

  scanf("%s", a+1);
  n=strlen(a+1);

  if(!can(1,n)) {
    printf("-1\n");
    return 0;
  }

  /*pos[1]=0;
  for(i=2;i<=n;i++) {
    if(a[i]==a[i-1]) {
      pos[i]=i-1;
      continue;
    }
    else {
      stack < char > s;
      where=max(pos[i-1]-1,0);
      s.push(a[i]);
      while(where>0) {
        if(s.top()==a[where]) {
          s.pop();
          if(s.empty()) break;
        }
        else {
          s.push(a[where]);
        }
        --where;
      }
      pos[i]=where;
    }
  }*/

  pos[1]=0;
  for(i=2;i<=n;i++) {
    where=i-1;
    while(where>0 && a[where]!=a[i]) where=pos[where]-1;
    pos[i]=max(where,0);
  }

  //for(i=1;i<=n;i++) printf("pos [ %d ] = %d\n", i, pos[i]);

  solve(1,n);
  for(i=1;i<=n;i++) {
    printf("%c", ans[i]);
  }
  printf("\n");

  return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a+1);
   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 2 ms 568 KB Output is correct
8 Correct 2 ms 568 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 6 ms 1008 KB Output is correct
13 Correct 6 ms 1148 KB Output is correct
14 Correct 7 ms 1320 KB Output is correct
15 Correct 8 ms 1320 KB Output is correct
16 Correct 7 ms 1320 KB Output is correct
17 Correct 7 ms 1320 KB Output is correct
18 Correct 8 ms 1320 KB Output is correct
19 Correct 8 ms 1456 KB Output is correct
20 Correct 6 ms 1456 KB Output is correct
21 Correct 9 ms 1576 KB Output is correct