제출 #101359

#제출 시각아이디문제언어결과실행 시간메모리
101359ZwariowanyMarcin회문 (APIO14_palindrome)C++14
0 / 100
382 ms11584 KiB
#include <bits/stdc++.h> #define pb push_back #define ll long long #define ss(v) (int)v.size() #define fi first #define se second using namespace std; const int nax = 2 * 300100; char c[nax]; int kmr[nax]; pair < pair < int, int > , int > help[nax]; int gdzie[nax]; int lcp[nax]; stack < pair < int, int > > s; int lewo[nax], prawo[nax]; int main() { scanf("%s", c + 1); int n = strlen(c + 1); ll ans = n; for(int i = 1; n >= i; ++i) kmr[i] = c[i]; for(int j = 1; 1000 > j; ++j) { for(int i = 1; n >= i; ++i) help[i] = {{kmr[i], kmr[i + (1 << (j - 1))]}, i}; sort(help + 1, help + n + 1); int cnt = 1; for(int i = 1; n >= i; ++i) { kmr[help[i].se] = cnt; if(help[i].fi != help[i + 1].fi) cnt++; } if(cnt == n + 1) break; } for(int i = 1; n >= i; ++i) gdzie[kmr[i]] = i; int k = 0; for(int i = 1; n >= i; ++i) { while(c[i + k] == c[gdzie[kmr[i] + 1] + k]) k++; lcp[kmr[i]] = k; if(k) --k; } for(int i = 1; n >= i; ++i) lewo[i] = prawo[i] = i; for(int i = 1; n >= i; ++i) { while(!s.empty() && s.top().first > lcp[i]) { prawo[s.top().second] = i; s.pop(); } s.push({lcp[i], i}); } while(!s.empty()) s.pop(); for(int i = n; i >= 1; --i) { while(!s.empty() && s.top().first > lcp[i]) { lewo[s.top().second] = i + 1; s.pop(); } s.push({lcp[i], i}); } while(!s.empty()) { lewo[s.top().se] = 1; s.pop(); } for(int i = 1; n >= i; ++i) ans = max(ans, (ll)(lcp[i] * (prawo[i] - lewo[i] + 1))); printf("%lld", ans); }

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

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