QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#483408	#7364. 回文	TLE_AK	0	37ms	25100kb	C++14	1.3kb	2024-07-18 16:46:37	2024-07-18 16:46:42

Judging History

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

[2024-07-18 16:46:42]
评测

测评结果：0
用时：37ms
内存：25100kb

查看

[2024-07-18 16:46:37]
提交

answer

#include<bits/stdc++.h>
using namespace std;


namespace acac
{
	
	char S[2000010],C[500010];
	int dy[500010],p[2000010],st[1000010][30];

	int n,m,q;
	
	void read()
	{
		scanf("%s",C+1);
		n=strlen(C+1);
		S[++m]='?';
		S[++m]='$';
		for(int i=1;i<=n;i++)
		{
			S[++m]=C[i];
			dy[i]=m;
			S[++m]='$'; 
		}
		S[++m]='!';
	}
	
	int qr(int l,int r)
	{
		int k=log(r-l+1)/log(2);
		return max(st[l][k],st[r-(1<<k)+1][k]);
	 } 
	
	int  main()
	{
		read();
		int mid=0,r=0;
		for(int i=2;i<m;i++)
		{
			int w=mid*2-i;
			if(i<=r)p[i]=min(p[w],r-i+1);
			else p[i]=1;
			while(S[i+p[i]]==S[i-p[i]])
			{
				p[i]++;
			}
			if(i+p[i]>r)mid=i,r=i+p[i]-1;
			st[i][0]=p[i]-1;
			//cout<<st[i][0]<<' ';
		}
		for(int j=1;j<=20;j++)
		{
		
			for(int i=1;i<=m;i++)
			{
				st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
		}
		scanf("%d",&q);
		while(q--)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			a=dy[a]-1,b=dy[b]+1;
			int l=1,r=b-a+1,ans=1;
			
		//	cout<<l<<' '<<r<<endl;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				//cout<<mid<<endl;
				if(qr(a+mid-1,b-mid+1)>=mid)
				{
					ans=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			cout<<ans<<'\n';
		}
		return 0;
	}
}

int main()
{
	acac::main();
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Runtime Error

input:

kmojliclywcyevunhgfnumdzvncnmzbkxjsrkzlyguvjwqmyamvwvidqvfcwnkoolupcrjhynrnlmncqwntqaqtnwqcnmlnrnyhjrcpulooknwcfvqdivwvmaymqwjvugylzkrsmlabbmjltopjasklgawfdbosdlmwahaygutogtvoenkxddmehwokwybkpireouiqqlsfbuqslxjlusnwkzgadxtagewjlchtcezugeguzecthcljwegatxdagzkwnsuljxlsqwlkpvoajknflirxpqcxmyhcgimr
293
...

output:

result:

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 12196kb

input:

vesjaxxsumewkbahmdfohuzggavsskdplrjqgonwnvtqhqdvxwdvbbvdwxtostthmmzqckepyglcysblxcbcxlbsyclgylyqtthedcqvuoghiyfekmaycoiiumirusuzosmaijqpgrwgcnxtojzyxpnjzyzjnpxyzjotxncgwrgpqjiamsozusurimuiiocyamkefyihgouvpxqdkybihtpmfqfzlwzylmtpgzvzhcrygruvzztttbofobtttzzvurgyrchzvzgptmlyzwlzfqfmpthibykdqxpegpbglnzk...

output:

result:

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

Test #3:

score: 0

Wrong Answer

time: 0ms

memory: 14452kb

input:

anuahqplebjsacgumhxqolpgrxqcqzlhxrdthilfysevwdukoaksysixdggqzfjifopilugpdlrihgriaedgcjljuzdyqnyplpovdlvsitjcizogkcjkipzwnbdugpkkcghcpcioksqbnvfeggpzdfcxddppanaqnjdrtczcurvgdhnhuuxmktusuykwqrpjgauznlzcgxahiumnbeendsvdoflmuqaylnmsxgfdelfljnvlkeftwsvqhrxpnyjfwohdomcrqcxhvfvksfkjaihqiksfwdlopmwyhagelhju...

output:

result:

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

Test #4:

score: 0

Wrong Answer

time: 0ms

memory: 12936kb

input:

mfvckuykhckfuqmontrmfcfttxsqnaenocsvdxafpwkpftcwtqwgtsihvaquaudwebxmdijlcrenvivcwbwccmjyxmgmuhdkesgmkcbasghbbwlutayipathsvawcdkkmbdkdiurfsytgjasgsrebgtyjlclkycanipjqlpvxtusmetaxpkwvgilcqnspilinqanxofgxjwqzphraildqdewozyndxbekdknrvbdjgwwvulxfdaqpsziqmrtvlzcabcnouwilynyrbzktbfsfaepmyfjbwuuhvxihiyjicox...

output:

result:

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

Test #5:

score: 0

Wrong Answer

time: 0ms

memory: 11372kb

input:

piliegnejflgljiidtifmgpcwttkfqexweatzcfecoyuyzpyayapbnenfvjbimyuttkjimtuzpoyhfugdivlxyebblrvgkwowzftkjxjopepbcdkcrioyjjscqnvycmaicuijcdkzizgtyskrkgyflmfvtntfnuikjqyblajyhygopbgpmxruwkkkuqszuuxhorfzsyzgpnxcuifrlvieeeavsrrgthetamjemxekupmclxitasqoqrokhtvomrjlksomhagdxyarqqoqhzuiqlhinhizujhkziqnabxnguz...

output:

result:

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

Test #6:

score: 0

Runtime Error

input:

syucmgkigdlpevdxsshewqirqqcdljqjgaugkvzplmidhvwxeuhuzmzscczopnaviqlgnavpezpquyupilccvjsqfxjmpcsefwerqlgfitezkaffvdwlyhilzflbjecsikzvyecgpjkucqukkrauolgzffotznjxmbvcmsuzrwstehxgqzygfjfybzmyuoxvshelxlpzfxwalgxzlwvhsbaikzsgjkzvzjmlbhgubzcunksleqdgulmysfjashpwjymspmtoxiwaiimcbdqbbudlwbptrusyumtszzwbpmgg...

output:

result:

Test #7:

score: 0

Wrong Answer

time: 22ms

memory: 21836kb

input:

acfojkhxkvgskemxswoddjrxylgurlpfkpkhssmaqavonpjkhozprsffoslcluvabbpmynaucitshgbfrhilbxuyvdeilculqepksnsosdruqnzkrismdmpypuwigcwmlrynryysiazxaikbsvsxhwobtxuriupwxfmotimszqrfqqcfcukzmghijkeibpndndbodgzpuzqyznrjpzykhzmgrcxhexbsjmanfybqvojzbwpyttmrneejcpdncuzcjdmgxevqmbltpkotcywnfglumjpldxytuaahbgdcnges...

output:

result:

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

Test #8:

score: 0

Wrong Answer

time: 33ms

memory: 25072kb

input:

aaxvxlcltrlilgqvklenrxdcqzouiizataquwymdxtkzyenpdefayzmwugrysrxpwznxpesvcglwqokoajclkeiadelfupalmwhpceexzuzethlcuidgwekhrzvacntvtfmlqptdszlphlewmmwzwcdmjwpefntdlcdrrhejjhakjpkglpbyooqkdhkzrswpmlseuqobyzrquhtdqlbfegkolncwaqoyxrmelvysykpsschwcghzecwneoklalscjqgxoqilbisabofjebktbbzomfupjqcupolpowbtazlq...

output:

result:

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

Test #9:

score: 0

Runtime Error

input:

bydjourdrgeaxhanforissxtcbtoqpcslsmsuipplgpyitlspqplflboqptqnahqwzchrjhifexlgnmbsehwkwjzojfwvhmmuatwkozdvqwxcorhmhirdgzkztmzegneseslmxuuoifnakuwsycrcgkzpnspyvvfrcbutiknycrvsqgglsvritrrmilxhhrtclxzslysblwsimexxkodgizphdapogypdudlssdispudgxhnfidsyivbvgamsujzzelovuilauyzmstgpgqipmhnbqskffrjjfnzhotbnlzk...

output:

result:

Test #10:

score: 0

Wrong Answer

time: 37ms

memory: 24664kb

input:

hsfcfbhlqerzkkwsyslalaslnahwpqqhkflavreluedfhcprzyfaipqyzaupdypfannefsdhimxnxoxbaqfktuqcgkjhskocyzeyyvbimybpixxgygccyqjcysqsylrhqrblfqrvheoolimkvqejywdjeuzbhhqdafuybfkarmacprqkqadbrfsrehhthtginqqhwdukdzjfrtgyepxmrnpmrokehpzxtnbigekjlvwkeofqrayiodxshtdbiisdyrboacqktisjtdkfuzmuzrmhgdqewukdcufjrqtskxjk...

output:

result:

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

Test #11:

score: 0

Wrong Answer

time: 36ms

memory: 25100kb

input:

uqgylihdxuhtoedyzgzsnwjfaxxdrbadecbkxhbwvzztggrcvorlbgdobvnlswamdnehzepqdqeajrhfwkavapzqvbivztnsqtqnjxjejpgokdyyfxrsuxblzpftwbdkxvrczcerpjadlkqxieyslegpwgwuvzixavdbbtzcvuvnyjpjqvzfzcdnypukljhlspedodczoamlqokdljxdwtonfavmwxemmwicpfbcxfriiqymwizfjghzskzsxyzpluyjwvwyjjzjdddhoflaizakyjzmjmucfxrowqmiiiqp...

output:

result:

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

Test #12:

score: 0

Runtime Error

input:

senpfhuxjnjduvkehgshpecrhtmrsjqaeosajatkkrtdwodqmsfmvoxyipcqjddyxbrroqpkhujinzclqudwqhehxvbpsdqnxzhkjoipcqkqddetmordwjpsuqzoerllzmzbwuorrbmwbzjoycmpeyotbhcwdxygeeqgxbwcqlrywyruatywmmvgckvaowvjpeegwhzarnabqopxpkbtrkhyqauthnzkdmmfdxxfawxygtuzmmbdzhxhstkgtjgzaprjstmssfpczmyyqryfxycoimzobpbihnnmsocfegkc...

output:

result:

Test #13:

score: 0

Runtime Error

input:

nwsiebavjnlnjifvaylnhfzybafysczcmrzplqehpgkavzaddjbltazcotufbdzxetxrwhshlxgoqdvbwrkeqkhsbujudbcjhahwkbluvnvdvdxnwocvdkjilwcziqdivzvdlbfwzdenmqlienvoqveubtdoszndqutfsguooniomoyblyxteyhpwommzvnumpwmzqafvfgmnokjwwnkdofoikamvlrxrfkvmrxmsrknmojvaumkrsrlgnpriipbnsbqvglegyhjdefpjngwtbknuivlyftjlsxgffnsjvib...

output:

result:

Test #14:

score: 0

Wrong Answer

time: 37ms

memory: 21824kb

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

Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaytvhrajhtxhttnnlmeqimzzsjscccivbyritmiznnvgksdehrtmiwacnbixkxnjytuzimzssogvxaemlcpkdtimzfxqreghsbnsqpkwcfepbisgnmispquhyzeqapvpjdfjelclvezqsdjxndhuwxloghiljexxirocvfcpgrilpxspmzjkvhyifkptzguxohzyyjuxqahbblayluiktzmrsgrhthdypkigvjqngfuwkchfepqfvhyuyunfrhluvcdyhvbpktdfoyy...

output:

result:

Test #17:

score: 0

Runtime Error

input:

aaaazkvsgnabokhungreeglngwrtynocgzehwlqgkiiiqdloxdezdcdbhriugyqfqhhaproemijuhymtacrerxmwdzzputjzucaygdskcwpvxdvuafnpfttarbksdowftsieylqlmpcvyrvhtdorechiduhgxkicaicbrcploefuuzmucorweejnscoepoijalirxzxrxbkksvuimwavmhxhhwndfkwocguaojzgtpxwtjmlrkbpbwvjtcilnyjjkmymvwaylhgmobosditopkpmmsawqlricifwcnwvxqac...

output:

result:

Test #18:

score: 0

Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaebhhrvkfkvewwgcwzupqagltrbvbpsmrzhqqrzpphdatdovtqcskottjjaijncilycjoqvhjbvaorrczwefumogmkipliwrjgjcmcksniyjpowbzpezlmkkiivhadolbahzjlelwurmdhfktndmcqndtbimufcsilykijsbmlqrxlfkimnzghkxgtqgznzgcgmrkygvzbdizbraghkncugpszudehqyuhkywdzdbitixbamapwgzbzknwypluul...

output:

result:

Test #19:

score: 0

Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaalvgbspddxrtwkccxskalmiaahvuaaevjkzxskmumnesqsjfqlgkanmmdinkbiabnrmvocequrnicjqzdatwwdzpgyoumwymnsjnklvbjrswytpqejlgxcmoaqqvpihlghjrsyvcoxhvprkfusafjsdrgopnfufkoopyqetppxuciqcwjxldgtwcthdepfcxdvrrhxcxdmsjnukgpdgkknnwzwmtavzvynhsapujivwmjlsaybeuaftemhzpmuexavqmhvpfou...

output:

result:

Test #20:

score: 0

Runtime Error

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaairvzomrstpfklvpyiboqxtnqbjazhstswwhmrdgbzsstvkrtencmmeqjfclkztnlsrrghcfrfrivxfrrpnwehishsneqljlmqwkugitnkuotmncikpvxzvgxcvdppekdbomsvqupgpjdcowzqfoxcivupvucxstsjlrlylvlzmqcxtqdwztpxmzetubgxllckejlkwjytrvdwmimdencuffcdifrllsoihxnbhoyy...