Submission #59589

#	Time	Username	Problem	Language	Result	Execution time	Memory
59589		octopuses	Match (CEOI16_match)	C++17	100 / 100	39 ms	14084 KiB

match

//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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63