QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#802651 | #8668. 回文路径 | flowing_boat | 20 | 28ms | 15656kb | C++14 | 6.9kb | 2024-12-07 14:17:44 | 2024-12-07 14:17:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO{
#define IOSIZE (1<<20)
char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
#ifdef ONLINE_JUDGE
#define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif
#define isdigit(ch)(ch>47&&ch<58)
#define isspace(ch)(ch<33)
template <typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*1+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}inline bool read(bool&b){char ch;while(ch=getchar(),isspace(ch));b=ch^48;return true;}inline void print(bool b){putchar(b+48);}template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a),print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}jyt;template<typename T>Fast_IO&operator>>(Fast_IO&jyt,T&b){return read(b),jyt;}template<typename T>Fast_IO&operator<<(Fast_IO&jyt,T b){return print(b),jyt;}
struct IO{static const int S=1<<21;char buf[S],*p1,*p2;int st[105],Top;~IO(){clear();}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}IO&operator>>(char&x){while(x=gc(),x==' '||x=='\n');return*this;}template<typename T>IO&operator>>(T&x){x=0;bool f=0;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f^=1;ch=gc();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc();f?x=-x:0;return*this;}IO&operator<<(const char c){pc(c);return*this;}template<typename T>IO&operator<<(T x){if(x<0)pc('-'),x=-x;do{st[++st[0]]=x%10,x/=10;}while(x);while(st[0]){pc('0'+st[st[0]--]);}return*this;}}ld;
} using namespace fast_IO;
#define ll long long
#define ull unsigned long long
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define rep(i, l, r) for (int i = l; i < r ; ++i)
#define per(i, l, r) for (int i = l; i > r ; --i)
namespace RPD {
#define pf(x) ((x) * (x))
#define ppf(x) ((x) * (x) * (x))
#define modf(x, mod) (((x) % mod + mod) % mod)
#define min3(x, y, z) (min(x, min(y, z)))
#define min4(x, y, z, w) (min(min(x, y), min(z, w)))
#define max3(x, y, z) (max(x, max(y, z)))
#define max4(x, y, z, w) (max(max(x, y), max(z, w)))
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
#define lowbit(x) (x & -x)
#define bitcount(x) __builtin_popcount(x)
#define albit(x) ((1 << (x)) - 1)
#define mkbit(x) (1 << (x))
#define gtbit(x, id) (((x) >> (id)) & 1)
}
// #define ld cin
// #define jyt cout
// #define int long long
const int N = 2e5 + 7;
const int inf = 1e9 + 7;
const ll linf = 1e18 + 7;
const ll Base = 2077;
const ll P = 998244353;
namespace JoKing {
int n, Ans = 0; string S[2];
ll base[N], lxl[30];
struct HASH {
ll H[2][N];
inline ll gh(int op, int l, int r) {return (H[op][r] - H[op][l - 1] + P) * base[n - r] % P;}
inline ll fgh(int op, int l, int r) {return gh(op, n - r + 1, n - l + 1);}
} A, B;
inline void solve() {
REP(i, 1, n) { // Mid = i(0)
int L = 1, R = min(i, n - i + 1), Res1 = 0, Res2 = 0;
while (L <= R) {
int mid = (L + R) >> 1;
if (A.gh(0, i - mid + 1, i) == B.fgh(0, i, i + mid - 1)) L = mid + 1, Res1 = mid;
else R = mid - 1;
} Ans = max(Ans, Res1 * 2 - 1);
L = 1, R = min(i - Res1, n - (i + Res1 - 1) + 1), Res2 = 0;
while (L <= R) {
int mid = (L + R) >> 1;
if (A.gh(0, i - Res1 - mid + 1, i - Res1) == B.fgh(1, i + Res1 - 1, i + Res1 - 1 + mid - 1)) L = mid + 1, Res2 = mid;
else R = mid - 1;
} Ans = max(Ans, (Res1 + Res2) * 2 - 1);
}
REP(i, 1, n - 1) { // Mid = i(0) ~ i + 1(0)
int L = 1, R = min(i, n - i), Res1 = 0, Res2 = 0;
while (L <= R) {
int mid = (L + R) >> 1;
if (A.gh(0, i - mid + 1, i) == B.fgh(0, i + 1, i + mid)) L = mid + 1, Res1 = mid;
else R = mid - 1;
} Ans = max(Ans, Res1 * 2);
if (!Res1) break;
L = 1, R = min(i - Res1, n - (i + Res1) + 1), Res2 = 0;
while (L <= R) {
int mid = (L + R) >> 1;
if (A.gh(0, i - Res1 - mid + 1, i - Res1) == B.fgh(1, i + Res1, i + Res1 + mid - 1)) L = mid + 1, Res2 = mid;
else R = mid - 1;
} Ans = max(Ans, (Res1 + Res2) * 2);
}
}
signed main() { srand(114514);
jyt >> n >> S[0] >> S[1], S[0] = " " + S[0], S[1] = " " + S[1], base[0] = 1;
REP(i, 0, 25) lxl[i] = rand();
REP(i, 1, n) {
base[i] = base[i - 1] * Base % P;
A.H[0][i] = (A.H[0][i - 1] + base[i - 1] * lxl[S[0][i] - 'a']) % P;
A.H[1][i] = (A.H[1][i - 1] + base[i - 1] * lxl[S[1][i] - 'a']) % P;
B.H[0][i] = (B.H[0][i - 1] + base[i - 1] * lxl[S[0][n - i + 1] - 'a']) % P;
B.H[1][i] = (B.H[1][i - 1] + base[i - 1] * lxl[S[1][n - i + 1] - 'a']) % P;
}
REP(i, 1, n) {
if (A.gh(0, i, i) != A.gh(1, i, i)) continue;
int L = 1, R = min(i, n - i + 1), Res = 0;
while (L <= R) {
int mid = (L + R) >> 1;
if (A.gh(0, i - mid + 1, i) == B.fgh(1, i, i + mid - 1)) L = mid + 1, Res = mid;
else R = mid - 1;
} Ans = max(Ans, Res * 2);
}
solve();
swap(A.H[0], A.H[1]), swap(B.H[0], B.H[1]), swap(A.H[0], B.H[0]), swap(A.H[1], B.H[1]);
solve();
jyt << Ans << '\n';
return 0;
}
}
signed main() {
// freopen("std.in", "r", stdin);
// freopen("user.out", "w", stdout);
// ios::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
JoKing::main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 14792kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
5
result:
wrong answer 1st lines differ - expected: '6', found: '5'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 21ms
memory: 13656kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 24ms
memory: 13872kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 28ms
memory: 15656kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 16ms
memory: 14288kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 25ms
memory: 14424kb
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok single line: '99999'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%