QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#742871#5085. Palindrome Typeucup-team5062#AC ✓2ms6420kbC++201.3kb2024-11-13 17:32:352024-11-13 17:32:35

Judging History

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

  • [2024-11-13 17:32:35]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:6420kb
  • [2024-11-13 17:32:35]
  • 提交

answer

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

int dp[100009][7];
int Answer = (1 << 30);
string S;

void update(int cl, int cr, int v) {
    int val = cl + cr;
    val -= (int)(S.size() - 1);
    val += 3;
    if (0 <= val && val <= 6) dp[cl][val] = min(dp[cl][val], v);
}

int main() {
    // Step 1. Input
    cin >> S;

    // Step 2. DP Init
    for (int i = 0; i < S.size(); i++) {
        for (int j = 0; j < 7; j++) dp[i][j] = (1 << 30);
    }
    dp[0][3] = 0;

    // Step 3. DP
    for (int i = 0; i < (int)S.size(); i++) {
        for (int j = 6; j >= 0; j--) {
            if (dp[i][j] == (1 << 30)) continue;
            int cl = i;
            int cr = (S.size() - 1 - i); cr += (j - 3);
            // cout << i << " " << j << " " << cl << " " << cr << " " << dp[i][j] << endl;
            if (cr - cl == -1 || cr - cl == 0) {
                Answer = min(Answer, dp[i][j]);
            }
            if (cl >= 0 && cr < (int)S.size()) {
                if (S[cl] == S[cr]) update(cl + 1, cr - 1, dp[i][j]);
                update(cl + 1, cr, dp[i][j] + 1);
                update(cl, cr - 1, dp[i][j] + 1);
            }
        }
    }

    // Step 4. Get Answer
    if (Answer >= 4) cout << "-1" << endl;
    else cout << Answer << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

aababaa

output:

0

result:

ok single line: '0'

Test #2:

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

input:

abccbbab

output:

2

result:

ok single line: '2'

Test #3:

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

input:

acmicpc

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

aabaa

output:

0

result:

ok single line: '0'

Test #5:

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

input:

abbaa

output:

1

result:

ok single line: '1'

Test #6:

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

input:

abcde

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

abcda

output:

2

result:

ok single line: '2'

Test #8:

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

input:

abaabba

output:

1

result:

ok single line: '1'

Test #9:

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

input:

bbbaaa

output:

3

result:

ok single line: '3'

Test #10:

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

input:

abbccba

output:

1

result:

ok single line: '1'

Test #11:

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

input:

abcabcb

output:

2

result:

ok single line: '2'

Test #12:

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

input:

bababbababb

output:

1

result:

ok single line: '1'

Test #13:

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

input:

bccaacacaaacaacaab

output:

3

result:

ok single line: '3'

Test #14:

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

input:

ienkzavpcizlzdhkhdzlzcpvzzknei

output:

3

result:

ok single line: '3'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

xebhsigufoeitoeotieofuygidshbx

output:

3

result:

ok single line: '3'

Test #16:

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

input:

dhnthbvccwreeksxyvrprgmtvxqsmfdpoqlwrgywdrrdwygrwlqopdfmsqxvtmgrprvyxskeerwccvbhtnhbd

output:

1

result:

ok single line: '1'

Test #17:

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

input:

iixcpzhlsmoymepzvowvhemuvyolonyylvxdnwkaqzoolugmguloozqakwndxvyynoloyvumehvwovzpemyomslhzpcxii

output:

1

result:

ok single line: '1'

Test #18:

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

input:

ktivgldiwuvvuwfuimxbwnfuxjbkveugxcddpjnnfliajowtcwuyjztglwqgcmozouefdssifakoqhhsfdtodowqmmypapymmqwodotdfshhqokafissdfeuozomcgqwlgtzjyuwctwojailfnnjpddcxguevkbjxufnwbxmiufwuvvuwidlgvitk

output:

0

result:

ok single line: '0'

Test #19:

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

input:

brawtvyoegtlxrsmihfugdhxevyofongrghnzcnqivjvuaogkvcryjqegqtlgiuxobmpfzfnwriqrywcuzvswknzreuekcaisiackeuerznkvsvzucwyrqirwnfzfpmbogxuigltqgeqjyrcvkgoauvjviqncznhgrgnofoyvexhdgufimsrxltgeoyvtwarb

output:

-1

result:

ok single line: '-1'

Test #20:

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

input:

bjrdlkkeuxwpuleskensyvgaoqpfqxpuiixwuhaohwgdjmvtsknsfwsvokdfhubqfyozhoqomytdxkoqdygvgcqdqaixhdyzkypllpykzydhxiaqdqcgvgydqokxtymoqohzoyfqbuhfdkovswfsnkstvmjdgwhoahuwxiiupxqfpqoagvysnerkselupwxuekkldrjb

output:

2

result:

ok single line: '2'

Test #21:

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

input:

xyrquyctbtomlifsvzqwszovnmwdxrvurmmmnqhqkxfxfkpcliydhoaxawcynyuhmjvzzcslaxjhjymugkxqzapbwrwbmpytehodisxuuwdefibqzkczcdzrfvkijcgcgnqlyljsffxjlabjmkelohkfoisxrudwatolrzwlhcispiubvynjfzruhjtbdwzfrnqkpnvwrfoofrwvnpkqnrfzwdbtjhurzfjnyvbuipsichlwzrlotawdurxsiofkholekmbaljxffsjlylqngcgcjikvfrzdczckzqbfedwu...

output:

3

result:

ok single line: '3'

Test #22:

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

input:

qcnwmzuexrrrhwsstqipfmfithltdizvmmsznmfkgydnuxhnnsetekbxtoqwyprkdllsasfgqivkgcavueoyqrxjhqhhhbunmffmakusvpfdufyqlpregopqgzxoarbmzibztvtqnythdrxrgoxpfmfllebnwccxndygarwnqpuviuopklerylflpgznlbkyeiggceuuvqpdkesxryorjtjroyrxsekdpqvuuecggieykblnzgplflyrelkpouivupqnwragydnxccwnbellfmfpmxogrxrdhtynqtvtzbiz...

output:

3

result:

ok single line: '3'

Test #23:

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

input:

oftswowkrbmtqnhocbhzylujkfczlllbqetptrzmvlhnbredslesyybigdirotugxpvsiwhfkotlfxqzkutiuwqabatrtnytcvllsuqcjlnqidquzlctitwjvpbpdbihwvsoqlszwhrhmjblvghfbdqwstlxuvfrrzhjkakjjbswlvhibonctdbozmltksmdswmeywphzhdkfnsgdhlxnmnmayhmruplsbpqzfzqpbslpurmhyamnmnoxlhdgsnfkdhzhpwyemwsdmsktlmzobdtcsnobihvlwsbjjkakjhz...

output:

-1

result:

ok single line: '-1'

Test #24:

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

input:

gflwyilnakfxxxbrebxqjyzoaxuqhxwncjmcsxpsjvrissbyuzjqfzpvzoppvoolqxxspwkjffbqzvrxpsnxsesrtkjqyxbpwyjmwtxeyyuzwnwlglkyqdrlncbnzdewdokcjjgkkajgnitvtevlhpwwrajrdopiebknksxushairudkazyhqufhuoazerkkswyfpxzjgcrxyxkyyihocmvzcwajnkvijtnytohbsbzzbsbhotyntjivknjawczvmcohiyykxyxrcgjzxpfywskkrezaouhfuqhyzakduria...

output:

2

result:

ok single line: '2'

Test #25:

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

input:

qpvpahejsenjqjravaqxyukdqfratgqkvlbxufhnlwybfpdcquzoqjrgoliiryugojxoedvtotrsygvayramijgoatzimxecjbqnglgxezrefofeghsqqagstfchdgkmkabsojpsiizpxetdnovfobykharmjbytcbnskfkunljkrfpevkkjmivvinhrqhmskamwhxqukbhcgwgdjqvnxyiuhxbaokniwpvswuiselzguynxhxnyugzlesiuwsvpwinkoabxhuiyxnqjdgwgchbkuqxhwmaksmhqrhnivvim...

output:

2

result:

ok single line: '2'

Test #26:

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

input:

vvpefnuxjwrigvnbfrusdhwtqqlpeqgbmvfricrtaiegdrikkeeolbhcrstxlzzxxgqfihbjrfrwyzgjelxpoetfzofmoejlmzsvjvgaaxxbzfkdqjuenqmoetauzlflnagwxowymvbnblstumyjemajfcdgolrbnazkovkcrlpuyhnuwneabgliipoycgbrgabuyozrbolawyuuoaupiiytxmrbuvscvvzvjymnmzpkyjgombduldpishlmedpbaoxmojzajonjztznwckhizraicomhdoktnwhwxkhlxsm...

output:

-1

result:

ok single line: '-1'

Test #27:

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

input:

eqejbhvitsyijlbloupxipxsczvunzmrprdsyadssbcemepcagclxzfzybunaghpzkkymnsfqujfaahbgjmdkreisyyuhfmgrwgdjaizvtextoybzmgkglualsvuzjdqfjwomgphaugvihzjthtbsqegkbckkfcpryddfsmhoseyzdivldwftcnedqqnvscothrycfhqylpzpzucetjyvxeznwokorzjyshayotwckxrjsvnnenkdtlqpadgtcpruzuspnqrxokiifxxmlhpgtiyvleopvhjwbemqwfpkqxu...

output:

1

result:

ok single line: '1'

Test #28:

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

input:

fsdarrxlmzsffruegoplsphgvvndlyissmujfrxrsrwyisergtcbiljgixlvxuprijbncagurcubuyucuyfelrmtoyqlufeeohrqhxnabhexiyzczhgkytgotybpeftunmnwlaxmjdlrdmvcteptzvhsvijzocwdqjzblypubaohmljipaboxjittrujvqmlbmommdjqfzxskgacjbsgmbziuwrsmefosucgzlwfmtxxczblatrputxrpqjduotoiwvijrnylmvnlyanrreombfduqhqecfpyczkvoiicfxn...

output:

2

result:

ok single line: '2'

Test #29:

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

input:

utwglhanestizpssmlspkuqfwsxehvcbqakdkkqoemyfbsyqeqfomxuirrpyotagtkjfubvapugrmejswqjjnftfykfodfuzrfeniaoywurkacdwsmhhtdolrnufrbbstiwgqyuqwqhhsjkpdyylrdzirvpkxqeqycyqbvhxlqgeaqvdqvqjzstsniekaicakdrnyynlotpqmmwckmojehdsshesrjtdmkrkkevaxntjbpolbcwilzcdigwbrrfddwpncnpbcildxbrbdpjorlsztqdlhiqmggzitqlxzway...

output:

1

result:

ok single line: '1'

Test #30:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

mjnrimbykkhyovdmoihymbmxrektnvxzhmsrzwpjiziwullivsjhvvgpbrioohpvukmtgeeofomzzxjxrugprngseoisxyqriemqirgnfsohsaelumcoziifyrawpqpzuerfvxucrjlllrxhezvdkejivjgmbynxcgczdxbwinitehakiyosczdzklnljaklinmlmojudrpjapujnkdrjgstufgdhqrpfdcrtmlydciesephosbxbtsxzyagqtwwzynumbtqddwxhnfvfiuibmfamijcdhaehozurumuxiug...

output:

0

result:

ok single line: '0'

Test #31:

score: 0
Accepted
time: 1ms
memory: 3880kb

input:

bhpkjaznrfnylldmqvvpnuhpkpwtdkrgugqdjpsaxfzkreyhbtyqoigaxetcrkiltzqeqiennfygmwopsogiwoiwubylnjyiiomawtomaosmmicgxkovawruzsipdgxlvmnrfdffryugiymhiddkzwgzqoqtvngszulgxrmrrgxzelhoomaqigrbxhuuudmwxxcwqqnhymheyquocuemdxpaemubpizofbkyuyfskozkgtbkohxtfotjapmpxldepqcjokdaycnfyopovohafamfryxokcszsxkihpjhswms...

output:

3

result:

ok single line: '3'

Test #32:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

uacxtttozkcjyxssksfpmxwymchyhsobssbllwbngfwgepyojfdveawredplvfppyqalmeyvlxbsmcgvhmtmopfsuwfrbugbminzonwckxuybcwlqpzegeycaevdadhnnwocjkgwjauleqyvhxbpdarfgmkirrvfnljxvpvfrpsviqqppufswyzcnjmebkjovsnrhkyyaqwkiobxiirehqiuzvycfktacitmtrmvjifrxgofrfkyxuuzpubweuzjdsvymhtvsynpgdwxlixidrhumjrqfqzkkwiwebsybhnk...

output:

1

result:

ok single line: '1'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

obncmueifwcccegxvkszhqkrnpmeyvmnwbpkxvsctufvaluvvmxfchwsxkwxfkmdnbpkwhopdtmehgbesyjxifphsnezzrfmuuytcmkhgznnfptapdxxkoecdlecejqydothaepidexktrkjujiexpjcangeywebmylpccxhgxtaoelkpvqpkbrkqyoowtsjtdyxhvenuzpifcuvynkiodvfbltyenjzqhwzecnzccjhheefropfskmvwivcvecolynqdarffaoogttxjifdtrbrbwtxbvlowyezbxgiyuwe...

output:

2

result:

ok single line: '2'

Test #34:

score: 0
Accepted
time: 1ms
memory: 4192kb

input:

bcqatarjdfzvabdynnqexqgutwlrxbtadjdyjujpzikbknbxcrezkkwdjhvgioinzlllhvagdmjncllecrembasmjnurddgeqrpymrgseqfgbskfjqunqmzzbwsgzykpqcpetwwzmchpwuwiksvbgwahstpttaljeaoxwmzkqgznayxlqsoxqogljwedwpoasezorabhhawjatwrnkogburmqxroniqhmsxfsypbznnzhjswwicxfvlvtdmilepzymfrlwumjhnqrgppqtmvpztiefqplhrktydguxsdhiwa...

output:

-1

result:

ok single line: '-1'

Test #35:

score: 0
Accepted
time: 1ms
memory: 4220kb

input:

lcilalfjkasdtvoaqixcyuskcezhfzgsepfgclponhriefixpgzncsagyzodawvenalpnafdkylqfwnucpighknhldklzhqnjbexbkankngqjtknkuurehypkkbltrydsfcvrelbtrrdmcqxwkqbtrsfbvrvmragweenippdiggukzrhlikfzekcabzmtbvrfzfpqwtyebspamymwirxmdbmhbbacytkxybnwulbwfsyrqkpadmohodorgqvejfbkhqgddjbidactktvqgmxwpnnvfiboqeaxujcxuehyelt...

output:

2

result:

ok single line: '2'

Test #36:

score: 0
Accepted
time: 1ms
memory: 4228kb

input:

wwjucpbthcaienbdkgxfwpptwgzxumytkhnnyoigsjowyrbixyqupfplnojkdjdpqqcognwywmxwdygbzwxoemctdndiwixmyccgpzhnlejpersdorsudwpijtqhbqvcsxkjyrykxjbcavfqmzkrvccgxsnakiceipngilsgwtkxqpncrawoeyvbskbdtghbvxjdkclhxveontsevoszopahackvktyhqhmbjykhvoxijpofgjguyjbynntxjrezbqckqmtmcqumgltmubiskktxzouiiakjrmvhbptdfqrl...

output:

2

result:

ok single line: '2'

Test #37:

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

input:

euajjxjlrejaxbyvxobwfcuruietgnnmhoxrlheelpfktfgqvhpbllufuyacooqxcoqpvxvimatfhzydipgtaaawbaarorosfhjcefmshfapgyuonajpcjmdmmucflvmugoyldsvismrqgffirxkcjqoxmrfxortuirilmdvepmxxuefnbppmhgmuzrtnknjsgrfswbxnpwkjarwcjoqqucktveigtrazlgsjjrxanjkpdirmykcsmpnivvqopqnayhjjyiknswdvewjdgnxvcldzivnxldxkkjtlrfylbbi...

output:

3

result:

ok single line: '3'

Test #38:

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

input:

ryqikpuwkabqupuqkxvqocdyzphkqsxksnsccobpqcflrzddzzundzneowphpmrhclmgznvppcahegkffgskfhouedbvsueufqaefyvvayeeeojlxdvcnjyrpbohvubcndisbepeetiikuvhzqlmbkfqnvxjqaldguxhapneiyousjbtzpgcbltohsxzvlebhbkjsynbydvsmzlnqrprfkfoffnaqtdzwpippxsnanfmorzekqxrddfikukanpbmejbugthgipuzgvfsndkqirasmmubbvpigqcmlluuaqvi...

output:

3

result:

ok single line: '3'

Test #39:

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

input:

qfwcuvpxrmdracykkzznjqjuohtsztqpaotwkitdxyuzcvmnwlafdmztvsounemptfmfqhipgfoiaaxwoadtocnjwbgmhsbczpjrxugdzvnbvnzlncfdgumcxsoeksjmhsdemkjnfzocmnobrvexpqcmlsqxkbjuupyizkwgjkkvaawtvctksvwfppdaqowmduveermpdxkfxizvkuffpekgtpglgcyjztqfmcvrbhxzqywcsbjjfwpalymrckddftjrxgkznhafhwkbxtkfpcfdcrwedbiiwtbuzmvovvud...

output:

-1

result:

ok single line: '-1'

Test #40:

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

input:

qepycslklynhzkkruaucaztyrazoomsgqhevzrfmpuvpefiahffieyixajlovfuomylnsschmxytfhvmoawuyfryoeomkicyjnobfqktpjmusijgkfcjmtjdxyphirirgwunmfgdqvykdhsnouybnkemkvuuoemuaihopprfkrrpajfpddsspyfbtbwhfkdfsmtibmpmejbgsgvwmpqdnvfgwbpdluidgdnisfwwoxeigagsrxvfsanrdfuozfsikhqcomaelfnrhtlyqjdlltcpyyfzdzhohzqxntczypsf...

output:

3

result:

ok single line: '3'

Test #41:

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

input:

pjpylsynxoiagfroxaynqykxlarebqcqcuqpmocjemlnredrfbevzptnrmtuevngpdxcuznanznfdqwkucgttbilnbfrzuaoyxquzgumhktmcpxwudsngaytegmdaotammunsrbzbvldkkaepsuvusoayddbrxbfjysdpucqrpvdcxkrrenmwbmxgsyyrbfczyhoulglaeqcbautejhbkvatnargbwkdwrtscaffgwjhwfcbojebfguugndjlnokficjkkoqgazefchulnvstrnbesnrfbbmjgwtqmlymles...

output:

1

result:

ok single line: '1'

Test #42:

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

input:

bcqatarjdfzvabdynnqexqgutwlrxbtadjdyjujpzikbknbxcrezkkwdjhvgioinzlllhvagdmjncllecrembasmjnurddgeqrpymrgseqfgbskfjqunqmzzbwsgzykpqcpetwwzmchpwuwiksvbgwahstpttaljeaoxwmzkqgznayxlqsoxqogljwedwpoasezorabhhawjatwrnkogburmqxroniqhmsxfsypbznnzhjswwicxfvlvtdmilepzymfrlwumjhnqrgppqtmvpztiefqplhrktydguxsdhiwa...

output:

-1

result:

ok single line: '-1'

Test #43:

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

input:

vfitessxgeejhcxbbtxlnvvrhzfvngpkoxespwpxavgjafnbykolfjfnlkiatzkhwobnmqlpntynzlqxwgjdqosdacdtbncxedlqvyflreaqrrqpxbtprnsrqvnrlprpvefqclbvrcokveauhvkyiepacesnulcpphhtujonneyikaerxopfvfixjamflowcxevunljcqhmajqughjocqwbcynhldenaikwxxgbnpnqzdkhkvxomtrotexghbtklfikdolsgakhgwossmhehyudfrjovfygkjtpxgkfhumpt...

output:

2

result:

ok single line: '2'