QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#557330 | #8668. 回文路径 | h_rains | 0 | 4ms | 8468kb | C++14 | 3.1kb | 2024-09-11 09:00:21 | 2024-09-11 09:00:22 |
answer
bool M1;
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db double
#define LD long double
#define Pii pair<int,int>
#define Pll pair<ll,ll>
#define Pull pair<ull,ull>
#define Pdb pair<db,db>
#define fir first
#define sec second
#define vec vector<int>
#define pb push_back
#define qlr cerr<<"qlr\n"
#define dyh cerr<<"dyh\n"
#define pc(x) __builtin_popcount(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define look_memory cerr<<'\n'<<abs(&M1-&M2)/1024.0/1024<<'\n'
#define look_time cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n'
mt19937 rng(time(0)^(*new int));
const ll INF=0x3f3f3f3f3f3f3f3f;
const int Mod=1e9+7;
template<typename T>
inline void inc(T &a,T b){
if(b<0) b+=Mod;
a+=b;
if(a>=Mod) a-=Mod;
}
template<typename T>
inline void dec(T &a,T b){
if(b<0) b+=Mod;
a-=b;
if(a<0) a+=Mod;
}
template<typename T>
inline void muc(T &a,T b){
a=a*b%Mod;
}
template<typename T>
inline bool chkmin(T &a,T b){
if(a<=b) return false;
a=b;
return true;
}
template<typename T>
inline bool chkmax(T &a,T b){
if(a>=b) return false;
a=b;
return true;
}
const int base=131;
int n,ans;
char a[100010],b[100010],s1[200010],s2[200010];
int lp1[200010],lp2[200010];
ull pw[100010],h1[100010],h2[100010];
void mnc(int n,char *s,int *lp){
for(int i=1,mid=0,r=0;i<=n;i++){
if(i<=r) lp[i]=min(lp[2*i-mid],r-i+1);
while(s[i-lp[i]]==s[i+lp[i]]) lp[i]++;
if(chkmax(r,i+lp[i]-1)) mid=i;
}
}
bool chk(int a,int b,int c,int d){
if(a<1||b>n||c<1||d>n||a>b||c>d) return 0;
c=n-c+1,d=n-d+1,swap(c,d);
return (h1[b]-h1[a-1])*pw[a]==(h2[d]-h2[c-1])*pw[c];
}
void init(){
#define N 100000
pw[0]=1;
F(i,1,N) pw[i]=pw[i-1]*base;
#undef N
}
bool M2;
int main(){
// freopen("trade.in","r",stdin);
// freopen("trade.out","w",stdout);
srand(time(0)^(*new int));
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
cin>>n;
cin>>(a+1);
cin>>(b+1);
F(i,1,n) h1[i]=h1[i-1]+a[i]*pw[n-i];
F(i,1,n) h2[i]=h2[i-1]+b[n-i+1]*pw[n-i];
F(i,1,n) s1[i*2-1]='#',s1[i*2]=a[i];
s1[2*n+1]='#',s1[0]='~';
mnc(2*n+1,s1,lp1);
F(i,1,n) s2[i*2-1]='#',s2[i*2]=b[i];
s2[2*n+1]='#',s2[0]='~';
mnc(2*n+1,s2,lp2);
F(i,1,2*n+1) chkmax(ans,lp1[i]-1);
F(i,1,2*n+1) chkmax(ans,lp2[i]-1);
// F(i,2,2*n){
// int l=(i-lp1[i])/2+1,r=(i+lp1[i])/2-1;
// if(l>r) continue;
// if(chk(1,l-1,r,r+l-2)) chkmax(ans,i);
// }
// F(i,2,2*n){
// int l=(i-lp2[i])/2+1,r=(i+lp2[i])/2-1;
// if(l>r) continue;
// if(chk(1,l,r,r+l-1)) chkmax(ans,i);
// }
cout<<ans;
look_memory;
look_time;
return 0;
}
/*
g++ A1.cpp -o A1 -std=c++14 -O2 -Wall -Wextra -fno-ms-extensions&&./A1
5
pkusc
pkukp
6
bbacdg
efabba
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 1ms
memory: 6084kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 5824kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
4
result:
wrong answer 1st lines differ - expected: '7', found: '4'
Subtask #2:
score: 0
Time Limit Exceeded
Test #11:
score: 20
Accepted
time: 0ms
memory: 8448kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 3ms
memory: 8468kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 4ms
memory: 8404kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 2ms
memory: 8460kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 0
Time Limit Exceeded
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
0%