Submission #110861

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
110861	2019-05-12 16:09:41	mosesmayer	Match (CEOI16_match)	C++17	100 / 100	19 ms	11776 KiB

match

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mxsz = 1e5 + 5;
int n;
char S[mxsz], ans[mxsz];
int lft[mxsz][26];
void prec(){
  for (int i = 1, p; i <= n; i++){
    p = S[i] - 'a';
    lft[i][p] = i;
    if (i - 1)
      for (int j = 0, x = lft[i-1][p]; j < 26; j++)
        if (x && (j^p))
          lft[i][j] = lft[x-1][j]; // link to before prev to be able to match prev with i
  }
  //for (int i = 1; i <= n; i++) for (int j = 0; j < 26; j++) cout << lft[i][j] << " \n"[j==25];
}
stack<int> st;
inline bool CHECK(){
  for (int i = 1, p; i <= n; i++){
    p = S[i] - 'a';
    if (st.empty() || st.top() != p) st.push(p);
    else st.pop();
  }
  return st.empty();
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63