QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#484707	#7364. 回文	tjsyykkk	0	541ms	210696kb	C++11	1.1kb	2024-07-19 21:43:54	2024-07-19 21:43:54

Judging History

你现在查看的是最新测评结果

[2024-07-19 21:43:54]
评测

测评结果：0
用时：541ms
内存：210696kb

查看

[2024-07-19 21:43:54]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,T,w[1000005],st[2000005][25],lg[2000005];
char s[1000005];
int change(int n){
	static char tmp[1000005];
	int m=0;tmp[++m]='$';
	for(int i=1;i<=n;i++)tmp[++m]=s[i],tmp[++m]='$';
	for(int i=1;i<=m;i++)s[i]=tmp[i];
	return m;
}
void manacher(int n){
	for(int i=2,p=1;i<=n;i++){
		if(i<=p+w[p])w[i]=min(p+w[p]-i,w[2*p-i]);
		while(i+w[i]+1<=n&&i-w[i]-1>=1&&s[i+w[i]+1]==s[i-w[i]-1])w[i]++;
		if(p+w[p]<i+w[i])p=i;
	}
}
void init(){
	memset(st,128,sizeof(st));
	for(int i=1;i<=n;i++)st[i][0]=w[i];
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int query(int l,int r){
	int t=lg[r-l+1];
	return max(st[l][t],st[r-(1<<t)+1][t]);
}
signed main(){
	scanf("%s",s+1);n=strlen(s+1);
	n=change(n);manacher(n);
	scanf("%d",&T);
	init();
	while(T--){
		int l,r;scanf("%d%d",&l,&r);
		l=l*2-1,r=r*2+1;
		int ans=1,ll=1,rr=r-l+1,mid=0;
		while(ll<=rr){
			mid=(ll+rr)>>1;
			if(query(l+mid-1,r-mid+1)>=mid)ans=mid,ll=mid+1;
			else rr=mid-1;
		}
		printf("%d\n",ans);
	}
}

Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 8ms

memory: 201980kb

input:

kmojliclywcyevunhgfnumdzvncnmzbkxjsrkzlyguvjwqmyamvwvidqvfcwnkoolupcrjhynrnlmncqwntqaqtnwqcnmlnrnyhjrcpulooknwcfvqdivwvmaymqwjvugylzkrsmlabbmjltopjasklgawfdbosdlmwahaygutogtvoenkxddmehwokwybkpireouiqqlsfbuqslxjlusnwkzgadxtagewjlchtcezugeguzecthcljwegatxdagzkwnsuljxlsqwlkpvoajknflirxpqcxmyhcgimr
293
...

output:

result:

wrong answer 2nd lines differ - expected: '75', found: '76'

Test #2:

score: 0

Wrong Answer

time: 12ms

memory: 199564kb

input:

vesjaxxsumewkbahmdfohuzggavsskdplrjqgonwnvtqhqdvxwdvbbvdwxtostthmmzqckepyglcysblxcbcxlbsyclgylyqtthedcqvuoghiyfekmaycoiiumirusuzosmaijqpgrwgcnxtojzyxpnjzyzjnpxyzjotxncgwrgpqjiamsozusurimuiiocyamkefyihgouvpxqdkybihtpmfqfzlwzylmtpgzvzhcrygruvzztttbofobtttzzvurgyrchzvzgptmlyzwlzfqfmpthibykdqxpegpbglnzk...

output:

result:

wrong answer 1st lines differ - expected: '81', found: '82'

Test #3:

score: 0

Wrong Answer

time: 7ms

memory: 201332kb

input:

anuahqplebjsacgumhxqolpgrxqcqzlhxrdthilfysevwdukoaksysixdggqzfjifopilugpdlrihgriaedgcjljuzdyqnyplpovdlvsitjcizogkcjkipzwnbdugpkkcghcpcioksqbnvfeggpzdfcxddppanaqnjdrtczcurvgdhnhuuxmktusuykwqrpjgauznlzcgxahiumnbeendsvdoflmuqaylnmsxgfdelfljnvlkeftwsvqhrxpnyjfwohdomcrqcxhvfvksfkjaihqiksfwdlopmwyhagelhju...

output:

result:

wrong answer 3rd lines differ - expected: '594', found: '595'

Test #4:

score: 0

Wrong Answer

time: 8ms

memory: 200888kb

input:

mfvckuykhckfuqmontrmfcfttxsqnaenocsvdxafpwkpftcwtqwgtsihvaquaudwebxmdijlcrenvivcwbwccmjyxmgmuhdkesgmkcbasghbbwlutayipathsvawcdkkmbdkdiurfsytgjasgsrebgtyjlclkycanipjqlpvxtusmetaxpkwvgilcqnspilinqanxofgxjwqzphraildqdewozyndxbekdknrvbdjgwwvulxfdaqpsziqmrtvlzcabcnouwilynyrbzktbfsfaepmyfjbwuuhvxihiyjicox...

output:

result:

wrong answer 2nd lines differ - expected: '1193', found: '1194'

Test #5:

score: 0

Wrong Answer

time: 19ms

memory: 199316kb

input:

piliegnejflgljiidtifmgpcwttkfqexweatzcfecoyuyzpyayapbnenfvjbimyuttkjimtuzpoyhfugdivlxyebblrvgkwowzftkjxjopepbcdkcrioyjjscqnvycmaicuijcdkzizgtyskrkgyflmfvtntfnuikjqyblajyhygopbgpmxruwkkkuqszuuxhorfzsyzgpnxcuifrlvieeeavsrrgthetamjemxekupmclxitasqoqrokhtvomrjlksomhagdxyarqqoqhzuiqlhinhizujhkziqnabxnguz...

output:

result:

wrong answer 9th lines differ - expected: '603', found: '604'

Test #6:

score: 0

Wrong Answer

time: 3ms

memory: 201940kb

input:

syucmgkigdlpevdxsshewqirqqcdljqjgaugkvzplmidhvwxeuhuzmzscczopnaviqlgnavpezpquyupilccvjsqfxjmpcsefwerqlgfitezkaffvdwlyhilzflbjecsikzvyecgpjkucqukkrauolgzffotznjxmbvcmsuzrwstehxgqzygfjfybzmyuoxvshelxlpzfxwalgxzlwvhsbaikzsgjkzvzjmlbhgubzcunksleqdgulmysfjashpwjymspmtoxiwaiimcbdqbbudlwbptrusyumtszzwbpmgg...

output:

result:

wrong answer 11th lines differ - expected: '1231', found: '1232'

Test #7:

score: 0

Wrong Answer

time: 20ms

memory: 200540kb

input:

acfojkhxkvgskemxswoddjrxylgurlpfkpkhssmaqavonpjkhozprsffoslcluvabbpmynaucitshgbfrhilbxuyvdeilculqepksnsosdruqnzkrismdmpypuwigcwmlrynryysiazxaikbsvsxhwobtxuriupwxfmotimszqrfqqcfcukzmghijkeibpndndbodgzpuzqyznrjpzykhzmgrcxhexbsjmanfybqvojzbwpyttmrneejcpdncuzcjdmgxevqmbltpkotcywnfglumjpldxytuaahbgdcnges...

output:

result:

wrong answer 1st lines differ - expected: '5769', found: '5770'

Test #8:

score: 0

Wrong Answer

time: 36ms

memory: 202096kb

input:

aaxvxlcltrlilgqvklenrxdcqzouiizataquwymdxtkzyenpdefayzmwugrysrxpwznxpesvcglwqokoajclkeiadelfupalmwhpceexzuzethlcuidgwekhrzvacntvtfmlqptdszlphlewmmwzwcdmjwpefntdlcdrrhejjhakjpkglpbyooqkdhkzrswpmlseuqobyzrquhtdqlbfegkolncwaqoyxrmelvysykpsschwcghzecwneoklalscjqgxoqilbisabofjebktbbzomfupjqcupolpowbtazlq...

output:

result:

wrong answer 1st lines differ - expected: '3297', found: '3298'

Test #9:

score: 0

Wrong Answer

time: 27ms

memory: 202212kb

input:

bydjourdrgeaxhanforissxtcbtoqpcslsmsuipplgpyitlspqplflboqptqnahqwzchrjhifexlgnmbsehwkwjzojfwvhmmuatwkozdvqwxcorhmhirdgzkztmzegneseslmxuuoifnakuwsycrcgkzpnspyvvfrcbutiknycrvsqgglsvritrrmilxhhrtclxzslysblwsimexxkodgizphdapogypdudlssdispudgxhnfidsyivbvgamsujzzelovuilauyzmstgpgqipmhnbqskffrjjfnzhotbnlzk...

output:

result:

wrong answer 1st lines differ - expected: '10655', found: '10656'

Test #10:

score: 0

Wrong Answer

time: 32ms

memory: 202872kb

input:

hsfcfbhlqerzkkwsyslalaslnahwpqqhkflavreluedfhcprzyfaipqyzaupdypfannefsdhimxnxoxbaqfktuqcgkjhskocyzeyyvbimybpixxgygccyqjcysqsylrhqrblfqrvheoolimkvqejywdjeuzbhhqdafuybfkarmacprqkqadbrfsrehhthtginqqhwdukdzjfrtgyepxmrnpmrokehpzxtnbigekjlvwkeofqrayiodxshtdbiisdyrboacqktisjtdkfuzmuzrmhgdqewukdcufjrqtskxjk...

output:

result:

wrong answer 1st lines differ - expected: '10616', found: '10617'

Test #11:

score: 0

Wrong Answer

time: 37ms

memory: 202132kb

input:

uqgylihdxuhtoedyzgzsnwjfaxxdrbadecbkxhbwvzztggrcvorlbgdobvnlswamdnehzepqdqeajrhfwkavapzqvbivztnsqtqnjxjejpgokdyyfxrsuxblzpftwbdkxvrczcerpjadlkqxieyslegpwgwuvzixavdbbtzcvuvnyjpjqvzfzcdnypukljhlspedodczoamlqokdljxdwtonfavmwxemmwicpfbcxfriiqymwizfjghzskzsxyzpluyjwvwyjjzjdddhoflaizakyjzmjmucfxrowqmiiiqp...

output:

result:

wrong answer 1st lines differ - expected: '5370', found: '5371'

Test #12:

score: 0

Wrong Answer

time: 19ms

memory: 203384kb

input:

senpfhuxjnjduvkehgshpecrhtmrsjqaeosajatkkrtdwodqmsfmvoxyipcqjddyxbrroqpkhujinzclqudwqhehxvbpsdqnxzhkjoipcqkqddetmordwjpsuqzoerllzmzbwuorrbmwbzjoycmpeyotbhcwdxygeeqgxbwcqlrywyruatywmmvgckvaowvjpeegwhzarnabqopxpkbtrkhyqauthnzkdmmfdxxfawxygtuzmmbdzhxhstkgtjgzaprjstmssfpczmyyqryfxycoimzobpbihnnmsocfegkc...

output:

result:

wrong answer 3rd lines differ - expected: '8596', found: '8597'

Test #13:

score: 0

Wrong Answer

time: 32ms

memory: 203648kb

input:

nwsiebavjnlnjifvaylnhfzybafysczcmrzplqehpgkavzaddjbltazcotufbdzxetxrwhshlxgoqdvbwrkeqkhsbujudbcjhahwkbluvnvdvdxnwocvdkjilwcziqdivzvdlbfwzdenmqlienvoqveubtdoszndqutfsguooniomoyblyxteyhpwommzvnumpwmzqafvfgmnokjwwnkdofoikamvlrxrfkvmrxmsrknmojvaumkrsrlgnpriipbnsbqvglegyhjdefpjngwtbknuivlyftjlsxgffnsjvib...

output:

result:

wrong answer 9th lines differ - expected: '9947', found: '9948'

Test #14:

score: 0

Wrong Answer

time: 37ms

memory: 200588kb

input:

uoqxubtwiuvrweemnisntsggdzuataqgegovblspuctnszgscxridxjlgibfbtdetqrhkfzzvbkbufeisycazjudefsyvgraenfjynszhdjtzidepogsvltustouvnviyrdsncubobnlkruzcsxsabwayfldakyslzfprixpbgpzlfneokxjtnmgtwipkddbmmeahowhndbnuymxryrkgolobkenugcpyfcelqpnpwwphnufpjcxwjyxlcsutfogqlepvyfcjohvhqivjefwtkwubjgtlsabqnpdpixgnrvw...

output:

result:

wrong answer 3rd lines differ - expected: '1762', found: '1763'

Test #15:

score: 0

Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaakkeiauuzvxheynhjstrlmdjuyadlukikotjzhqkfxlyabcfwkdyqkgsrkeqcpingbwuhlvlqcwrnotohwdcteumlrepoccfdfznrdltjbjkjzqkdiglyqxwbukxvlivpbhdtzdxsiaqyoqsykspneectkcrlupikmvnqqtbvicmjgwzonahfpytentjnwqunjlpalkwpcskwlqcarzzlktnklalcmplozonpmfpysuyqviwslsfhnzcbplzhyhs...

output:

result:

Test #16:

score: 0

Wrong Answer

time: 530ms

memory: 210584kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaytvhrajhtxhttnnlmeqimzzsjscccivbyritmiznnvgksdehrtmiwacnbixkxnjytuzimzssogvxaemlcpkdtimzfxqreghsbnsqpkwcfepbisgnmispquhyzeqapvpjdfjelclvezqsdjxndhuwxloghiljexxirocvfcpgrilpxspmzjkvhyifkptzguxohzyyjuxqahbblayluiktzmrsgrhthdypkigvjqngfuwkchfepqfvhyuyunfrhluvcdyhvbpktdfoyy...

output:

result:

wrong answer 3rd lines differ - expected: '37261', found: '37262'

Test #17:

score: 0

Wrong Answer

time: 517ms

memory: 209800kb

input:

aaaazkvsgnabokhungreeglngwrtynocgzehwlqgkiiiqdloxdezdcdbhriugyqfqhhaproemijuhymtacrerxmwdzzputjzucaygdskcwpvxdvuafnpfttarbksdowftsieylqlmpcvyrvhtdorechiduhgxkicaicbrcploefuuzmucorweejnscoepoijalirxzxrxbkksvuimwavmhxhhwndfkwocguaojzgtpxwtjmlrkbpbwvjtcilnyjjkmymvwaylhgmobosditopkpmmsawqlricifwcnwvxqac...

output:

result:

wrong answer 5th lines differ - expected: '25988', found: '25989'

Test #18:

score: 0

Wrong Answer

time: 541ms

memory: 210696kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaebhhrvkfkvewwgcwzupqagltrbvbpsmrzhqqrzpphdatdovtqcskottjjaijncilycjoqvhjbvaorrczwefumogmkipliwrjgjcmcksniyjpowbzpezlmkkiivhadolbahzjlelwurmdhfktndmcqndtbimufcsilykijsbmlqrxlfkimnzghkxgtqgznzgcgmrkygvzbdizbraghkncugpszudehqyuhkywdzdbitixbamapwgzbzknwypluul...

output:

result:

wrong answer 4th lines differ - expected: '34769', found: '34770'

Test #19:

score: 0

Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaalvgbspddxrtwkccxskalmiaahvuaaevjkzxskmumnesqsjfqlgkanmmdinkbiabnrmvocequrnicjqzdatwwdzpgyoumwymnsjnklvbjrswytpqejlgxcmoaqqvpihlghjrsyvcoxhvprkfusafjsdrgopnfufkoopyqetppxuciqcwjxldgtwcthdepfcxdvrrhxcxdmsjnukgpdgkknnwzwmtavzvynhsapujivwmjlsaybeuaftemhzpmuexavqmhvpfou...

output:

result:

Test #20:

score: 0

Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaairvzomrstpfklvpyiboqxtnqbjazhstswwhmrdgbzsstvkrtencmmeqjfclkztnlsrrghcfrfrivxfrrpnwehishsneqljlmqwkugitnkuotmncikpvxzvgxcvdppekdbomsvqupgpjdcowzqfoxcivupvucxstsjlrlylvlzmqcxtqdwztpxmzetubgxllckejlkwjytrvdwmimdencuffcdifrllsoihxnbhoyy...

output: