Task: | Longest palindrome |
Sender: | aalto2024j_003 |
Submission time: | 2024-11-06 16:36:38 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.03 s | details |
#4 | ACCEPTED | 0.03 s | details |
#5 | ACCEPTED | 0.04 s | details |
#6 | ACCEPTED | 0.04 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.03 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.01 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.02 s | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:60:20: warning: statement has no effect [-Wunused-value] 60 | #define debug(...) 42 | ^~ input/code.cpp:95:5: note: in expansion of macro 'debug' 95 | debug(p); | ^~~~~ input/code.cpp:60:20: warning: statement has no effect [-Wunused-value] 60 | #define debug(...) 42 | ^~ input/code.cpp:106:5: note: in expansion of macro 'debug' 106 | debug(ans, pos); | ^~~~~
Code
#pragma GCC optimize("O3","unroll-loops")#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i, a, b) for(int i = a; i < (b); ++i)#define all(x) begin(x), end(x)#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;string to_string(string s) {return '"' + s + '"';}string to_string(const char* s) {return to_string((string) s);}string to_string(bool b) {return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void debug_out() {cerr << endl;}template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}#ifdef LOCAL#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...) 42#endif/*** Author: User adamant on CodeForces* Source: http://codeforces.com/blog/entry/12143* Description: For each position in a string, computes p[0][i] = half length of* longest even palindrome around pos i, p[1][i] = longest odd (half rounded down).* Time: O(N)* Status: Stress-tested*/array<vi, 2> manacher(const string& s) {int n = sz(s);array<vi,2> p = {vi(n+1), vi(n)};rep(z,0,2) for (int i=0,l=0,r=0; i < n; i++) {int t = r-i+!z;if (i<r) p[z][i] = min(t, p[z][l+t]);int L = i-p[z][i], R = i+p[z][i]-!z;while (L>=1 && R+1<n && s[L-1] == s[R+1])p[z][i]++, L--, R++;if (R>r) l=L, r=R;}return p;}string s;int n;void solve() {cin >> s;n = sz(s);int ans = 0, pos = 0;auto p = manacher(s);debug(p);for (int i = 0; i < n; i++) {if (p[0][i] * 2 > ans) {ans = p[0][i] * 2;pos = i;}if (p[1][i] * 2 + 1 > ans) {ans = p[1][i] * 2 + 1;pos = i;}}debug(ans, pos);if (ans & 1) {int half = ans / 2;cout << s.substr(pos - half, ans);} else {int half = ans / 2;cout << s.substr(pos - half, ans);}}signed main() {cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit); // RTE if input wrong datatypesolve();}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
aaaaaaaaaa |
correct output |
---|
aaaaaaaaaa |
user output |
---|
aaaaaaaaaa |
Test 2
Verdict: ACCEPTED
input |
---|
ababababab |
correct output |
---|
ababababa |
user output |
---|
ababababa |
Test 3
Verdict: ACCEPTED
input |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
correct output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
user output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... Truncated |
Test 4
Verdict: ACCEPTED
input |
---|
ababababababababababababababab... |
correct output |
---|
ababababababababababababababab... |
user output |
---|
ababababababababababababababab... Truncated |
Test 5
Verdict: ACCEPTED
input |
---|
aztdvxzjwxtrludymvpradgbdpgnrq... |
correct output |
---|
aztdvxzjwxtrludymvpradgbdpgnrq... |
user output |
---|
aztdvxzjwxtrludymvpradgbdpgnrq... Truncated |
Test 6
Verdict: ACCEPTED
input |
---|
vvfigwwsyxbukedgcfyibvtbclybud... |
correct output |
---|
vvfigwwsyxbukedgcfyibvtbclybud... |
user output |
---|
vvfigwwsyxbukedgcfyibvtbclybud... Truncated |
Test 7
Verdict: ACCEPTED
input |
---|
abaabaaaaaaabaababbbbbbabaaabb... |
correct output |
---|
babbbabbbaabbbbaabbbbbbbbaabbb... |
user output |
---|
babbbabbbaabbbbaabbbbbbbbaabbb... |
Test 8
Verdict: ACCEPTED
input |
---|
txolestmgyepwrpofxyesjtsfkhjac... |
correct output |
---|
yxnbaabnxy |
user output |
---|
yxnbaabnxy |
Test 9
Verdict: ACCEPTED
input |
---|
ihpohpzoffel |
correct output |
---|
ff |
user output |
---|
ff |
Test 10
Verdict: ACCEPTED
input |
---|
flexflexvpqxierullgcfckjqflexf... |
correct output |
---|
cfc |
user output |
---|
cfc |
Test 11
Verdict: ACCEPTED
input |
---|
aabbabaabbaababbabaababbaabbab... |
correct output |
---|
abaababbaabbabaababbabaabbaaba... |
user output |
---|
abaababbaabbabaababbabaabbaaba... Truncated |
Test 12
Verdict: ACCEPTED
input |
---|
obsession |
correct output |
---|
ses |
user output |
---|
ses |
Test 13
Verdict: ACCEPTED
input |
---|
abcxcbaxcba |
correct output |
---|
abcxcba |
user output |
---|
abcxcba |
Test 14
Verdict: ACCEPTED
input |
---|
zzabc |
correct output |
---|
zz |
user output |
---|
zz |
Test 15
Verdict: ACCEPTED
input |
---|
aaccaabbaaccaaccaabbaaccaa |
correct output |
---|
aaccaabbaaccaaccaabbaaccaa |
user output |
---|
aaccaabbaaccaaccaabbaaccaa |
Test 16
Verdict: ACCEPTED
input |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
correct output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... |
user output |
---|
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa... Truncated |