제출 #52822

#제출 시각아이디문제언어결과실행 시간메모리
52822ainta괄호 문자열 (CEOI16_match)C++17
100 / 100
39 ms19900 KiB
#include<cstdio> #include<algorithm> #define N_ 101000 using namespace std; char p[N_], r[N_]; int n, D[N_][27], w[N_], Bef[N_][20]; int cur[N_], st[N_], top; bool OK(int b, int e) { if (b > e)return false; for (int i = 19; i >= 0; i--) { if (Bef[e][i] >= b)e = Bef[e][i]; } return b == e; } int main() { //freopen("input.txt", "r", stdin); int i, j; scanf("%s", p + 1); for (i = 1; p[i]; i++); n = i - 1; for (i = 1; i <= n; i++) { w[i] = p[i] - 'a' + 1; } for (i = 0; i <= n; i++) { Bef[i][0] = -1; for (j = 0; j <= 26; j++)D[i][j] = -1; D[i][w[i]] = 0; if (!i)continue; if (D[i - 1][w[i]] != -1) { int L = D[i - 1][w[i]] + 2; Bef[i][0] = i - L; if(w[i-L]!=w[i])D[i][w[i - L]] = L; for (j = 0; j <= 26; j++) { if (D[i - L][j] != -1) { if (D[i][j] == -1 || D[i][j] > D[i - L][j] + L)D[i][j] = D[i - L][j] + L; } } } } for (i = 0; i < 19; i++) { for (j = 1; j <= n; j++) { if (Bef[j][i] == -1)Bef[j][i + 1] = -1; else Bef[j][i + 1] = Bef[Bef[j][i]][i]; } } for (i = 1; i <= n; i++) { if (top && st[top] == w[i])top--; else st[++top] = w[i]; } if (top) { puts("-1"); return 0; } cur[0] = n; for (i = 1; i <= n; i++) { r[i] = '('; st[++top] = w[i]; int t = D[cur[top-1]][w[i]]; if (t == -1) { top -= 2; r[i] = ')'; continue; } cur[top] = cur[top - 1] - t - 1; if (!OK(i, cur[top])) { top -= 2; r[i] = ')'; continue; } } printf("%s\n", r + 1); }

컴파일 시 표준 에러 (stderr) 메시지

match.cpp: In function 'int main()':
match.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", p + 1);
  ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...