QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252578#5085. Palindrome TypeNYCU_gAwr_gurA#AC ✓48ms53312kbC++17813b2023-11-15 21:40:482023-11-15 21:40:49

Judging History

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

  • [2023-11-15 21:40:49]
  • 评测
  • 测评结果：AC
  • 用时：48ms
  • 内存：53312kb
查看
  • [2023-11-15 21:40:48]
  • 提交

answer

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

#ifdef DEBUG
#define fast
#else
#define fast cin.tie(0)->sync_with_stdio(0)
#define cerr if(1);else cerr
#define endl '\n'
#endif
#define _ <<' '<<
#define ALL(v) v.begin(),v.end()
#define ft first
#define sd second

using ll = long long;
using ld = long double;
using pii = pair<int,int>;

int n;
string s;
map<int,int> dp[100001], u[100001];

int sana(int l,int r)
{
	if(r-l+1<=1)
		return 0;
	if(abs(n-1-r-l)>3)
		return 4;
	if(u[l][r])
		return dp[l][r];
	u[l][r]=1;
	int res=4;
	if(s[l]==s[r])
		res=sana(l+1,r-1);
	res=min({res, sana(l+1,r)+1, sana(l,r-1)+1});
	return dp[l][r]=res;
}

signed main() {
	fast;
	
	cin>>s;
	n=s.size();
	int ans=sana(0,n-1);
	if(ans>3)
		ans=-1;
	cout<<ans<<endl;
	
	return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12764kb

input:

aababaa

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 12800kb

input:

abccbbab

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 12760kb

input:

acmicpc

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 12728kb

input:

aabaa

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 2ms
memory: 12616kb

input:

abbaa

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 0ms
memory: 12920kb

input:

abcde

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 12700kb

input:

abcda

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 0ms
memory: 12768kb

input:

abaabba

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 5ms
memory: 12760kb

input:

bbbaaa

output:

3

result:

ok single line: '3'

Test #10:

score: 0
Accepted
time: 0ms
memory: 12876kb

input:

abbccba

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 2ms
memory: 12672kb

input:

abcabcb

output:

2

result:

ok single line: '2'

Test #12:

score: 0
Accepted
time: 0ms
memory: 12760kb

input:

bababbababb

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 12764kb

input:

bccaacacaaacaacaab

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 2ms
memory: 12768kb

input:

ienkzavpcizlzdhkhdzlzcpvzzknei

output:

3

result:

ok single line: '3'

Test #15:

score: 0
Accepted
time: 0ms
memory: 12676kb

input:

xebhsigufoeitoeotieofuygidshbx

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 0ms
memory: 12904kb

input:

dhnthbvccwreeksxyvrprgmtvxqsmfdpoqlwrgywdrrdwygrwlqopdfmsqxvtmgrprvyxskeerwccvbhtnhbd

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 0ms
memory: 12788kb

input:

iixcpzhlsmoymepzvowvhemuvyolonyylvxdnwkaqzoolugmguloozqakwndxvyynoloyvumehvwovzpemyomslhzpcxii

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 0ms
memory: 12784kb

input:

ktivgldiwuvvuwfuimxbwnfuxjbkveugxcddpjnnfliajowtcwuyjztglwqgcmozouefdssifakoqhhsfdtodowqmmypapymmqwodotdfshhqokafissdfeuozomcgqwlgtzjyuwctwojailfnnjpddcxguevkbjxufnwbxmiufwuvvuwidlgvitk

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 0ms
memory: 12828kb

input:

brawtvyoegtlxrsmihfugdhxevyofongrghnzcnqivjvuaogkvcryjqegqtlgiuxobmpfzfnwriqrywcuzvswknzreuekcaisiackeuerznkvsvzucwyrqirwnfzfpmbogxuigltqgeqjyrcvkgoauvjviqncznhgrgnofoyvexhdgufimsrxltgeoyvtwarb

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 0ms
memory: 12996kb

input:

bjrdlkkeuxwpuleskensyvgaoqpfqxpuiixwuhaohwgdjmvtsknsfwsvokdfhubqfyozhoqomytdxkoqdygvgcqdqaixhdyzkypllpykzydhxiaqdqcgvgydqokxtymoqohzoyfqbuhfdkovswfsnkstvmjdgwhoahuwxiiupxqfpqoagvysnerkselupwxuekkldrjb

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 0ms
memory: 12908kb

input:

xyrquyctbtomlifsvzqwszovnmwdxrvurmmmnqhqkxfxfkpcliydhoaxawcynyuhmjvzzcslaxjhjymugkxqzapbwrwbmpytehodisxuuwdefibqzkczcdzrfvkijcgcgnqlyljsffxjlabjmkelohkfoisxrudwatolrzwlhcispiubvynjfzruhjtbdwzfrnqkpnvwrfoofrwvnpkqnrfzwdbtjhurzfjnyvbuipsichlwzrlotawdurxsiofkholekmbaljxffsjlylqngcgcjikvfrzdczckzqbfedwu...

output:

3

result:

ok single line: '3'

Test #22:

score: 0
Accepted
time: 0ms
memory: 13116kb

input:

qcnwmzuexrrrhwsstqipfmfithltdizvmmsznmfkgydnuxhnnsetekbxtoqwyprkdllsasfgqivkgcavueoyqrxjhqhhhbunmffmakusvpfdufyqlpregopqgzxoarbmzibztvtqnythdrxrgoxpfmfllebnwccxndygarwnqpuviuopklerylflpgznlbkyeiggceuuvqpdkesxryorjtjroyrxsekdpqvuuecggieykblnzgplflyrelkpouivupqnwragydnxccwnbellfmfpmxogrxrdhtynqtvtzbiz...

output:

3

result:

ok single line: '3'

Test #23:

score: 0
Accepted
time: 0ms
memory: 12944kb

input:

oftswowkrbmtqnhocbhzylujkfczlllbqetptrzmvlhnbredslesyybigdirotugxpvsiwhfkotlfxqzkutiuwqabatrtnytcvllsuqcjlnqidquzlctitwjvpbpdbihwvsoqlszwhrhmjblvghfbdqwstlxuvfrrzhjkakjjbswlvhibonctdbozmltksmdswmeywphzhdkfnsgdhlxnmnmayhmruplsbpqzfzqpbslpurmhyamnmnoxlhdgsnfkdhzhpwyemwsdmsktlmzobdtcsnobihvlwsbjjkakjhz...

output:

-1

result:

ok single line: '-1'

Test #24:

score: 0
Accepted
time: 0ms
memory: 12992kb

input:

gflwyilnakfxxxbrebxqjyzoaxuqhxwncjmcsxpsjvrissbyuzjqfzpvzoppvoolqxxspwkjffbqzvrxpsnxsesrtkjqyxbpwyjmwtxeyyuzwnwlglkyqdrlncbnzdewdokcjjgkkajgnitvtevlhpwwrajrdopiebknksxushairudkazyhqufhuoazerkkswyfpxzjgcrxyxkyyihocmvzcwajnkvijtnytohbsbzzbsbhotyntjivknjawczvmcohiyykxyxrcgjzxpfywskkrezaouhfuqhyzakduria...

output:

2

result:

ok single line: '2'

Test #25:

score: 0
Accepted
time: 0ms
memory: 12940kb

input:

qpvpahejsenjqjravaqxyukdqfratgqkvlbxufhnlwybfpdcquzoqjrgoliiryugojxoedvtotrsygvayramijgoatzimxecjbqnglgxezrefofeghsqqagstfchdgkmkabsojpsiizpxetdnovfobykharmjbytcbnskfkunljkrfpevkkjmivvinhrqhmskamwhxqukbhcgwgdjqvnxyiuhxbaokniwpvswuiselzguynxhxnyugzlesiuwsvpwinkoabxhuiyxnqjdgwgchbkuqxhwmaksmhqrhnivvim...

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 5ms
memory: 13128kb

input:

vvpefnuxjwrigvnbfrusdhwtqqlpeqgbmvfricrtaiegdrikkeeolbhcrstxlzzxxgqfihbjrfrwyzgjelxpoetfzofmoejlmzsvjvgaaxxbzfkdqjuenqmoetauzlflnagwxowymvbnblstumyjemajfcdgolrbnazkovkcrlpuyhnuwneabgliipoycgbrgabuyozrbolawyuuoaupiiytxmrbuvscvvzvjymnmzpkyjgombduldpishlmedpbaoxmojzajonjztznwckhizraicomhdoktnwhwxkhlxsm...

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 0ms
memory: 13316kb

input:

eqejbhvitsyijlbloupxipxsczvunzmrprdsyadssbcemepcagclxzfzybunaghpzkkymnsfqujfaahbgjmdkreisyyuhfmgrwgdjaizvtextoybzmgkglualsvuzjdqfjwomgphaugvihzjthtbsqegkbckkfcpryddfsmhoseyzdivldwftcnedqqnvscothrycfhqylpzpzucetjyvxeznwokorzjyshayotwckxrjsvnnenkdtlqpadgtcpruzuspnqrxokiifxxmlhpgtiyvleopvhjwbemqwfpkqxu...

output:

1

result:

ok single line: '1'

Test #28:

score: 0
Accepted
time: 0ms
memory: 13144kb

input:

fsdarrxlmzsffruegoplsphgvvndlyissmujfrxrsrwyisergtcbiljgixlvxuprijbncagurcubuyucuyfelrmtoyqlufeeohrqhxnabhexiyzczhgkytgotybpeftunmnwlaxmjdlrdmvcteptzvhsvijzocwdqjzblypubaohmljipaboxjittrujvqmlbmommdjqfzxskgacjbsgmbziuwrsmefosucgzlwfmtxxczblatrputxrpqjduotoiwvijrnylmvnlyanrreombfduqhqecfpyczkvoiicfxn...

output:

2

result:

ok single line: '2'

Test #29:

score: 0
Accepted
time: 2ms
memory: 13184kb

input:

utwglhanestizpssmlspkuqfwsxehvcbqakdkkqoemyfbsyqeqfomxuirrpyotagtkjfubvapugrmejswqjjnftfykfodfuzrfeniaoywurkacdwsmhhtdolrnufrbbstiwgqyuqwqhhsjkpdyylrdzirvpkxqeqycyqbvhxlqgeaqvdqvqjzstsniekaicakdrnyynlotpqmmwckmojehdsshesrjtdmkrkkevaxntjbpolbcwilzcdigwbrrfddwpncnpbcildxbrbdpjorlsztqdlhiqmggzitqlxzway...

output:

1

result:

ok single line: '1'

Test #30:

score: 0
Accepted
time: 4ms
memory: 16596kb

input:

mjnrimbykkhyovdmoihymbmxrektnvxzhmsrzwpjiziwullivsjhvvgpbrioohpvukmtgeeofomzzxjxrugprngseoisxyqriemqirgnfsohsaelumcoziifyrawpqpzuerfvxucrjlllrxhezvdkejivjgmbynxcgczdxbwinitehakiyosczdzklnljaklinmlmojudrpjapujnkdrjgstufgdhqrpfdcrtmlydciesephosbxbtsxzyagqtwwzynumbtqddwxhnfvfiuibmfamijcdhaehozurumuxiug...

output:

0

result:

ok single line: '0'

Test #31:

score: 0
Accepted
time: 3ms
memory: 16972kb

input:

bhpkjaznrfnylldmqvvpnuhpkpwtdkrgugqdjpsaxfzkreyhbtyqoigaxetcrkiltzqeqiennfygmwopsogiwoiwubylnjyiiomawtomaosmmicgxkovawruzsipdgxlvmnrfdffryugiymhiddkzwgzqoqtvngszulgxrmrrgxzelhoomaqigrbxhuuudmwxxcwqqnhymheyquocuemdxpaemubpizofbkyuyfskozkgtbkohxtfotjapmpxldepqcjokdaycnfyopovohafamfryxokcszsxkihpjhswms...

output:

3

result:

ok single line: '3'

Test #32:

score: 0
Accepted
time: 3ms
memory: 16984kb

input:

uacxtttozkcjyxssksfpmxwymchyhsobssbllwbngfwgepyojfdveawredplvfppyqalmeyvlxbsmcgvhmtmopfsuwfrbugbminzonwckxuybcwlqpzegeycaevdadhnnwocjkgwjauleqyvhxbpdarfgmkirrvfnljxvpvfrpsviqqppufswyzcnjmebkjovsnrhkyyaqwkiobxiirehqiuzvycfktacitmtrmvjifrxgofrfkyxuuzpubweuzjdsvymhtvsynpgdwxlixidrhumjrqfqzkkwiwebsybhnk...

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 3ms
memory: 16940kb

input:

obncmueifwcccegxvkszhqkrnpmeyvmnwbpkxvsctufvaluvvmxfchwsxkwxfkmdnbpkwhopdtmehgbesyjxifphsnezzrfmuuytcmkhgznnfptapdxxkoecdlecejqydothaepidexktrkjujiexpjcangeywebmylpccxhgxtaoelkpvqpkbrkqyoowtsjtdyxhvenuzpifcuvynkiodvfbltyenjzqhwzecnzccjhheefropfskmvwivcvecolynqdarffaoogttxjifdtrbrbwtxbvlowyezbxgiyuwe...

output:

2

result:

ok single line: '2'

Test #34:

score: 0
Accepted
time: 9ms
memory: 21664kb

input:

bcqatarjdfzvabdynnqexqgutwlrxbtadjdyjujpzikbknbxcrezkkwdjhvgioinzlllhvagdmjncllecrembasmjnurddgeqrpymrgseqfgbskfjqunqmzzbwsgzykpqcpetwwzmchpwuwiksvbgwahstpttaljeaoxwmzkqgznayxlqsoxqogljwedwpoasezorabhhawjatwrnkogburmqxroniqhmsxfsypbznnzhjswwicxfvlvtdmilepzymfrlwumjhnqrgppqtmvpztiefqplhrktydguxsdhiwa...

output:

-1

result:

ok single line: '-1'

Test #35:

score: 0
Accepted
time: 9ms
memory: 21664kb

input:

lcilalfjkasdtvoaqixcyuskcezhfzgsepfgclponhriefixpgzncsagyzodawvenalpnafdkylqfwnucpighknhldklzhqnjbexbkankngqjtknkuurehypkkbltrydsfcvrelbtrrdmcqxwkqbtrsfbvrvmragweenippdiggukzrhlikfzekcabzmtbvrfzfpqwtyebspamymwirxmdbmhbbacytkxybnwulbwfsyrqkpadmohodorgqvejfbkhqgddjbidactktvqgmxwpnnvfiboqeaxujcxuehyelt...

output:

2

result:

ok single line: '2'

Test #36:

score: 0
Accepted
time: 11ms
memory: 21212kb

input:

wwjucpbthcaienbdkgxfwpptwgzxumytkhnnyoigsjowyrbixyqupfplnojkdjdpqqcognwywmxwdygbzwxoemctdndiwixmyccgpzhnlejpersdorsudwpijtqhbqvcsxkjyrykxjbcavfqmzkrvccgxsnakiceipngilsgwtkxqpncrawoeyvbskbdtghbvxjdkclhxveontsevoszopahackvktyhqhmbjykhvoxijpofgjguyjbynntxjrezbqckqmtmcqumgltmubiskktxzouiiakjrmvhbptdfqrl...

output:

2

result:

ok single line: '2'

Test #37:

score: 0
Accepted
time: 18ms
memory: 30188kb

input:

euajjxjlrejaxbyvxobwfcuruietgnnmhoxrlheelpfktfgqvhpbllufuyacooqxcoqpvxvimatfhzydipgtaaawbaarorosfhjcefmshfapgyuonajpcjmdmmucflvmugoyldsvismrqgffirxkcjqoxmrfxortuirilmdvepmxxuefnbppmhgmuzrtnknjsgrfswbxnpwkjarwcjoqqucktveigtrazlgsjjrxanjkpdirmykcsmpnivvqopqnayhjjyiknswdvewjdgnxvcldzivnxldxkkjtlrfylbbi...

output:

3

result:

ok single line: '3'

Test #38:

score: 0
Accepted
time: 14ms
memory: 28564kb

input:

ryqikpuwkabqupuqkxvqocdyzphkqsxksnsccobpqcflrzddzzundzneowphpmrhclmgznvppcahegkffgskfhouedbvsueufqaefyvvayeeeojlxdvcnjyrpbohvubcndisbepeetiikuvhzqlmbkfqnvxjqaldguxhapneiyousjbtzpgcbltohsxzvlebhbkjsynbydvsmzlnqrprfkfoffnaqtdzwpippxsnanfmorzekqxrddfikukanpbmejbugthgipuzgvfsndkqirasmmubbvpigqcmlluuaqvi...

output:

3

result:

ok single line: '3'

Test #39:

score: 0
Accepted
time: 20ms
memory: 28508kb

input:

qfwcuvpxrmdracykkzznjqjuohtsztqpaotwkitdxyuzcvmnwlafdmztvsounemptfmfqhipgfoiaaxwoadtocnjwbgmhsbczpjrxugdzvnbvnzlncfdgumcxsoeksjmhsdemkjnfzocmnobrvexpqcmlsqxkbjuupyizkwgjkkvaawtvctksvwfppdaqowmduveermpdxkfxizvkuffpekgtpglgcyjztqfmcvrbhxzqywcsbjjfwpalymrckddftjrxgkznhafhwkbxtkfpcfdcrwedbiiwtbuzmvovvud...

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0
Accepted
time: 31ms
memory: 52876kb

input:

qepycslklynhzkkruaucaztyrazoomsgqhevzrfmpuvpefiahffieyixajlovfuomylnsschmxytfhvmoawuyfryoeomkicyjnobfqktpjmusijgkfcjmtjdxyphirirgwunmfgdqvykdhsnouybnkemkvuuoemuaihopprfkrrpajfpddsspyfbtbwhfkdfsmtibmpmejbgsgvwmpqdnvfgwbpdluidgdnisfwwoxeigagsrxvfsanrdfuozfsikhqcomaelfnrhtlyqjdlltcpyyfzdzhohzqxntczypsf...

output:

3

result:

ok single line: '3'

Test #41:

score: 0
Accepted
time: 34ms
memory: 49128kb

input:

pjpylsynxoiagfroxaynqykxlarebqcqcuqpmocjemlnredrfbevzptnrmtuevngpdxcuznanznfdqwkucgttbilnbfrzuaoyxquzgumhktmcpxwudsngaytegmdaotammunsrbzbvldkkaepsuvusoayddbrxbfjysdpucqrpvdcxkrrenmwbmxgsyyrbfczyhoulglaeqcbautejhbkvatnargbwkdwrtscaffgwjhwfcbojebfguugndjlnokficjkkoqgazefchulnvstrnbesnrfbbmjgwtqmlymles...

output:

1

result:

ok single line: '1'

Test #42:

score: 0
Accepted
time: 37ms
memory: 52852kb

input:

bcqatarjdfzvabdynnqexqgutwlrxbtadjdyjujpzikbknbxcrezkkwdjhvgioinzlllhvagdmjncllecrembasmjnurddgeqrpymrgseqfgbskfjqunqmzzbwsgzykpqcpetwwzmchpwuwiksvbgwahstpttaljeaoxwmzkqgznayxlqsoxqogljwedwpoasezorabhhawjatwrnkogburmqxroniqhmsxfsypbznnzhjswwicxfvlvtdmilepzymfrlwumjhnqrgppqtmvpztiefqplhrktydguxsdhiwa...

output:

-1

result:

ok single line: '-1'

Test #43:

score: 0
Accepted
time: 48ms
memory: 53312kb

input:

vfitessxgeejhcxbbtxlnvvrhzfvngpkoxespwpxavgjafnbykolfjfnlkiatzkhwobnmqlpntynzlqxwgjdqosdacdtbncxedlqvyflreaqrrqpxbtprnsrqvnrlprpvefqclbvrcokveauhvkyiepacesnulcpphhtujonneyikaerxopfvfixjamflowcxevunljcqhmajqughjocqwbcynhldenaikwxxgbnpnqzdkhkvxomtrotexghbtklfikdolsgakhgwossmhehyudfrjovfygkjtpxgkfhumpt...

output:

2

result:

ok single line: '2'
English 繁體中文 简体中文

Server Time: 2024-12-02 14:43:00 | OpenSource Project