oj.uz

Submission #59589

# Submission time Handle Problem Language Result Execution time Memory
59589 2018-07-22T14:10:02 Z octopuses Match (CEOI16_match) C++17
100 / 100
 39 ms 14084 KB 
//Giorgi Kldiashvili

#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define M 1000000007ll

using namespace std;

const int N = 100020;

int n;
char ch[N];
int a[N], A[N][30], C[N];
stack < int > q;

int main()
{
  scanf("%s", &ch);
  n = strlen(ch);
  for(int i = 1; i <= n; ++ i) a[i] = ch[i - 1] - 'a';
  for(int i = 1; i <= n; ++ i)
  {
    if(!q.size() || a[q.top()] != a[i])
      q.push(i);
    else
      q.pop();
  }
  if(q.size()) return printf("-1"), 0;
  while(q.size()) q.pop();

  A[1][a[1]] = 1;
  for(int i = 1; i <= n; ++ i)
  {
    A[i][a[i]] = i;
    int c = A[i - 1][a[i]];
    if(c <= 1) continue;
    c --;
    for(int j = 0; j < 26; ++ j)
      A[i][j] = max(A[i][j], A[c][j]);
  }

  for(int i = 1; i <= n; ++ i)
  {
    if(q.empty())
    {
      q.push(i);
      printf("(");
      C[i] = A[n][a[i]];
      continue;
    }
    int c = A[C[q.top()] - 1][a[i]];
    if(c <= i)
    {
      q.pop();
      printf(")");
    } else
    {
      C[i] = c;
      q.push(i);
      printf("(");
    }
  }
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:21:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[100020]' [-Wformat=]
   scanf("%s", &ch);
               ~~~^
match.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &ch);
   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 664 KB Output is correct
6 Correct 4 ms 780 KB Output is correct
7 Correct 4 ms 780 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 3 ms 664 KB Output is correct
6 Correct 4 ms 780 KB Output is correct
7 Correct 4 ms 780 KB Output is correct
8 Correct 4 ms 1304 KB Output is correct
9 Correct 4 ms 1464 KB Output is correct
10 Correct 5 ms 1480 KB Output is correct
11 Correct 4 ms 1480 KB Output is correct
12 Correct 21 ms 8232 KB Output is correct
13 Correct 23 ms 8980 KB Output is correct
14 Correct 18 ms 9740 KB Output is correct
15 Correct 27 ms 11020 KB Output is correct
16 Correct 28 ms 11116 KB Output is correct
17 Correct 31 ms 11920 KB Output is correct
18 Correct 39 ms 12560 KB Output is correct
19 Correct 34 ms 13288 KB Output is correct
20 Correct 20 ms 13288 KB Output is correct
21 Correct 33 ms 14084 KB Output is correct