Submission #59580

#	Time	Username	Problem	Language	Result	Execution time	Memory
59580		octopuses	Match (CEOI16_match)	C++17	37 / 100	2054 ms	1324 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];
string a;
inline bool go(int v, stack < int > q)
{
  q.push(v);
  for(int i = v + 1; i <= n; ++ i)
  {
    if(!q.size() || a[q.top()] != a[i])
      q.push(i);
    else
      q.pop();
  }
  if(q.size())
    return false;
  return true;
}
stack < int > q;

int main()
{
  scanf("%s", &ch);
  a = "$" + string(ch) + "$";
  n = strlen(ch);
  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();
  q.push(1); printf("(");
  for(int i = 2; i <= n; ++ i)
  {
    if(!q.size() || a[q.top()] != a[i])
      q.push(i), printf("(");
    else
    {
      if(go(i, q))
        q.push(i), printf("(");
      else
        q.pop(), printf(")");
    }
  }
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:35:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[100020]' [-Wformat=]
   scanf("%s", &ch);
               ~~~^
match.cpp:35: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: 0 / 63