QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#700365#5085. Palindrome Typetamthegod#AC ✓28ms46104kbC++231.3kb2024-11-02 12:48:562024-11-02 12:49:01

Judging History

This is the latest submission verdict.

  • [2024-11-02 12:49:01]
  • Judged
  • Verdict: AC
  • Time: 28ms
  • Memory: 46104kb
  • [2024-11-02 12:48:56]
  • Submitted

answer

#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n;
string s;
map<int, int> f[4][maxN];
void ReadInput()
{
    cin >> s;
    n = s.size();
    s = ' ' + s;
}
int dp(int i, int l, int r)
{
    if(l >= r) return 0;
    if(f[i][l].find(r) != f[i][l].end()) return f[i][l][r];
    int& res = f[i][l][r];
    res = oo;
    if(s[l] == s[r]) res = dp(i, l + 1, r - 1);
    if(i < 3)
    {
        res = min(res, dp(i + 1, l + 1, r) + 1);
        res = min(res, dp(i + 1, l, r - 1) + 1);
    }
    return res;
}
void Solve()
{
    int res = dp(0, 1, n);
    if(res <= 3) cout << res;
    else cout << -1;
}
#define taskname "sol"
int32_t main()
{
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        //freopen(taskname ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    //cin >> T;
    for(int itest=1; itest<=T; itest++)
    {
        ReadInput();
        Solve();
    }
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 22464kb

input:

aababaa

output:

0

result:

ok single line: '0'

Test #2:

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

input:

abccbbab

output:

2

result:

ok single line: '2'

Test #3:

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

input:

acmicpc

output:

-1

result:

ok single line: '-1'

Test #4:

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

input:

aabaa

output:

0

result:

ok single line: '0'

Test #5:

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

input:

abbaa

output:

1

result:

ok single line: '1'

Test #6:

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

input:

abcde

output:

-1

result:

ok single line: '-1'

Test #7:

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

input:

abcda

output:

2

result:

ok single line: '2'

Test #8:

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

input:

abaabba

output:

1

result:

ok single line: '1'

Test #9:

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

input:

bbbaaa

output:

3

result:

ok single line: '3'

Test #10:

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

input:

abbccba

output:

1

result:

ok single line: '1'

Test #11:

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

input:

abcabcb

output:

2

result:

ok single line: '2'

Test #12:

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

input:

bababbababb

output:

1

result:

ok single line: '1'

Test #13:

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

input:

bccaacacaaacaacaab

output:

3

result:

ok single line: '3'

Test #14:

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

input:

ienkzavpcizlzdhkhdzlzcpvzzknei

output:

3

result:

ok single line: '3'

Test #15:

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

input:

xebhsigufoeitoeotieofuygidshbx

output:

3

result:

ok single line: '3'

Test #16:

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

input:

dhnthbvccwreeksxyvrprgmtvxqsmfdpoqlwrgywdrrdwygrwlqopdfmsqxvtmgrprvyxskeerwccvbhtnhbd

output:

1

result:

ok single line: '1'

Test #17:

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

input:

iixcpzhlsmoymepzvowvhemuvyolonyylvxdnwkaqzoolugmguloozqakwndxvyynoloyvumehvwovzpemyomslhzpcxii

output:

1

result:

ok single line: '1'

Test #18:

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

input:

ktivgldiwuvvuwfuimxbwnfuxjbkveugxcddpjnnfliajowtcwuyjztglwqgcmozouefdssifakoqhhsfdtodowqmmypapymmqwodotdfshhqokafissdfeuozomcgqwlgtzjyuwctwojailfnnjpddcxguevkbjxufnwbxmiufwuvvuwidlgvitk

output:

0

result:

ok single line: '0'

Test #19:

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

input:

brawtvyoegtlxrsmihfugdhxevyofongrghnzcnqivjvuaogkvcryjqegqtlgiuxobmpfzfnwriqrywcuzvswknzreuekcaisiackeuerznkvsvzucwyrqirwnfzfpmbogxuigltqgeqjyrcvkgoauvjviqncznhgrgnofoyvexhdgufimsrxltgeoyvtwarb

output:

-1

result:

ok single line: '-1'

Test #20:

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

input:

bjrdlkkeuxwpuleskensyvgaoqpfqxpuiixwuhaohwgdjmvtsknsfwsvokdfhubqfyozhoqomytdxkoqdygvgcqdqaixhdyzkypllpykzydhxiaqdqcgvgydqokxtymoqohzoyfqbuhfdkovswfsnkstvmjdgwhoahuwxiiupxqfpqoagvysnerkselupwxuekkldrjb

output:

2

result:

ok single line: '2'

Test #21:

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

input:

xyrquyctbtomlifsvzqwszovnmwdxrvurmmmnqhqkxfxfkpcliydhoaxawcynyuhmjvzzcslaxjhjymugkxqzapbwrwbmpytehodisxuuwdefibqzkczcdzrfvkijcgcgnqlyljsffxjlabjmkelohkfoisxrudwatolrzwlhcispiubvynjfzruhjtbdwzfrnqkpnvwrfoofrwvnpkqnrfzwdbtjhurzfjnyvbuipsichlwzrlotawdurxsiofkholekmbaljxffsjlylqngcgcjikvfrzdczckzqbfedwu...

output:

3

result:

ok single line: '3'

Test #22:

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

input:

qcnwmzuexrrrhwsstqipfmfithltdizvmmsznmfkgydnuxhnnsetekbxtoqwyprkdllsasfgqivkgcavueoyqrxjhqhhhbunmffmakusvpfdufyqlpregopqgzxoarbmzibztvtqnythdrxrgoxpfmfllebnwccxndygarwnqpuviuopklerylflpgznlbkyeiggceuuvqpdkesxryorjtjroyrxsekdpqvuuecggieykblnzgplflyrelkpouivupqnwragydnxccwnbellfmfpmxogrxrdhtynqtvtzbiz...

output:

3

result:

ok single line: '3'

Test #23:

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

input:

oftswowkrbmtqnhocbhzylujkfczlllbqetptrzmvlhnbredslesyybigdirotugxpvsiwhfkotlfxqzkutiuwqabatrtnytcvllsuqcjlnqidquzlctitwjvpbpdbihwvsoqlszwhrhmjblvghfbdqwstlxuvfrrzhjkakjjbswlvhibonctdbozmltksmdswmeywphzhdkfnsgdhlxnmnmayhmruplsbpqzfzqpbslpurmhyamnmnoxlhdgsnfkdhzhpwyemwsdmsktlmzobdtcsnobihvlwsbjjkakjhz...

output:

-1

result:

ok single line: '-1'

Test #24:

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

input:

gflwyilnakfxxxbrebxqjyzoaxuqhxwncjmcsxpsjvrissbyuzjqfzpvzoppvoolqxxspwkjffbqzvrxpsnxsesrtkjqyxbpwyjmwtxeyyuzwnwlglkyqdrlncbnzdewdokcjjgkkajgnitvtevlhpwwrajrdopiebknksxushairudkazyhqufhuoazerkkswyfpxzjgcrxyxkyyihocmvzcwajnkvijtnytohbsbzzbsbhotyntjivknjawczvmcohiyykxyxrcgjzxpfywskkrezaouhfuqhyzakduria...

output:

2

result:

ok single line: '2'

Test #25:

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

input:

qpvpahejsenjqjravaqxyukdqfratgqkvlbxufhnlwybfpdcquzoqjrgoliiryugojxoedvtotrsygvayramijgoatzimxecjbqnglgxezrefofeghsqqagstfchdgkmkabsojpsiizpxetdnovfobykharmjbytcbnskfkunljkrfpevkkjmivvinhrqhmskamwhxqukbhcgwgdjqvnxyiuhxbaokniwpvswuiselzguynxhxnyugzlesiuwsvpwinkoabxhuiyxnqjdgwgchbkuqxhwmaksmhqrhnivvim...

output:

2

result:

ok single line: '2'

Test #26:

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

input:

vvpefnuxjwrigvnbfrusdhwtqqlpeqgbmvfricrtaiegdrikkeeolbhcrstxlzzxxgqfihbjrfrwyzgjelxpoetfzofmoejlmzsvjvgaaxxbzfkdqjuenqmoetauzlflnagwxowymvbnblstumyjemajfcdgolrbnazkovkcrlpuyhnuwneabgliipoycgbrgabuyozrbolawyuuoaupiiytxmrbuvscvvzvjymnmzpkyjgombduldpishlmedpbaoxmojzajonjztznwckhizraicomhdoktnwhwxkhlxsm...

output:

-1

result:

ok single line: '-1'

Test #27:

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

input:

eqejbhvitsyijlbloupxipxsczvunzmrprdsyadssbcemepcagclxzfzybunaghpzkkymnsfqujfaahbgjmdkreisyyuhfmgrwgdjaizvtextoybzmgkglualsvuzjdqfjwomgphaugvihzjthtbsqegkbckkfcpryddfsmhoseyzdivldwftcnedqqnvscothrycfhqylpzpzucetjyvxeznwokorzjyshayotwckxrjsvnnenkdtlqpadgtcpruzuspnqrxokiifxxmlhpgtiyvleopvhjwbemqwfpkqxu...

output:

1

result:

ok single line: '1'

Test #28:

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

input:

fsdarrxlmzsffruegoplsphgvvndlyissmujfrxrsrwyisergtcbiljgixlvxuprijbncagurcubuyucuyfelrmtoyqlufeeohrqhxnabhexiyzczhgkytgotybpeftunmnwlaxmjdlrdmvcteptzvhsvijzocwdqjzblypubaohmljipaboxjittrujvqmlbmommdjqfzxskgacjbsgmbziuwrsmefosucgzlwfmtxxczblatrputxrpqjduotoiwvijrnylmvnlyanrreombfduqhqecfpyczkvoiicfxn...

output:

2

result:

ok single line: '2'

Test #29:

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

input:

utwglhanestizpssmlspkuqfwsxehvcbqakdkkqoemyfbsyqeqfomxuirrpyotagtkjfubvapugrmejswqjjnftfykfodfuzrfeniaoywurkacdwsmhhtdolrnufrbbstiwgqyuqwqhhsjkpdyylrdzirvpkxqeqycyqbvhxlqgeaqvdqvqjzstsniekaicakdrnyynlotpqmmwckmojehdsshesrjtdmkrkkevaxntjbpolbcwilzcdigwbrrfddwpncnpbcildxbrbdpjorlsztqdlhiqmggzitqlxzway...

output:

1

result:

ok single line: '1'

Test #30:

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

input:

mjnrimbykkhyovdmoihymbmxrektnvxzhmsrzwpjiziwullivsjhvvgpbrioohpvukmtgeeofomzzxjxrugprngseoisxyqriemqirgnfsohsaelumcoziifyrawpqpzuerfvxucrjlllrxhezvdkejivjgmbynxcgczdxbwinitehakiyosczdzklnljaklinmlmojudrpjapujnkdrjgstufgdhqrpfdcrtmlydciesephosbxbtsxzyagqtwwzynumbtqddwxhnfvfiuibmfamijcdhaehozurumuxiug...

output:

0

result:

ok single line: '0'

Test #31:

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

input:

bhpkjaznrfnylldmqvvpnuhpkpwtdkrgugqdjpsaxfzkreyhbtyqoigaxetcrkiltzqeqiennfygmwopsogiwoiwubylnjyiiomawtomaosmmicgxkovawruzsipdgxlvmnrfdffryugiymhiddkzwgzqoqtvngszulgxrmrrgxzelhoomaqigrbxhuuudmwxxcwqqnhymheyquocuemdxpaemubpizofbkyuyfskozkgtbkohxtfotjapmpxldepqcjokdaycnfyopovohafamfryxokcszsxkihpjhswms...

output:

3

result:

ok single line: '3'

Test #32:

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

input:

uacxtttozkcjyxssksfpmxwymchyhsobssbllwbngfwgepyojfdveawredplvfppyqalmeyvlxbsmcgvhmtmopfsuwfrbugbminzonwckxuybcwlqpzegeycaevdadhnnwocjkgwjauleqyvhxbpdarfgmkirrvfnljxvpvfrpsviqqppufswyzcnjmebkjovsnrhkyyaqwkiobxiirehqiuzvycfktacitmtrmvjifrxgofrfkyxuuzpubweuzjdsvymhtvsynpgdwxlixidrhumjrqfqzkkwiwebsybhnk...

output:

1

result:

ok single line: '1'

Test #33:

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

input:

obncmueifwcccegxvkszhqkrnpmeyvmnwbpkxvsctufvaluvvmxfchwsxkwxfkmdnbpkwhopdtmehgbesyjxifphsnezzrfmuuytcmkhgznnfptapdxxkoecdlecejqydothaepidexktrkjujiexpjcangeywebmylpccxhgxtaoelkpvqpkbrkqyoowtsjtdyxhvenuzpifcuvynkiodvfbltyenjzqhwzecnzccjhheefropfskmvwivcvecolynqdarffaoogttxjifdtrbrbwtxbvlowyezbxgiyuwe...

output:

2

result:

ok single line: '2'

Test #34:

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

input:

bcqatarjdfzvabdynnqexqgutwlrxbtadjdyjujpzikbknbxcrezkkwdjhvgioinzlllhvagdmjncllecrembasmjnurddgeqrpymrgseqfgbskfjqunqmzzbwsgzykpqcpetwwzmchpwuwiksvbgwahstpttaljeaoxwmzkqgznayxlqsoxqogljwedwpoasezorabhhawjatwrnkogburmqxroniqhmsxfsypbznnzhjswwicxfvlvtdmilepzymfrlwumjhnqrgppqtmvpztiefqplhrktydguxsdhiwa...

output:

-1

result:

ok single line: '-1'

Test #35:

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

input:

lcilalfjkasdtvoaqixcyuskcezhfzgsepfgclponhriefixpgzncsagyzodawvenalpnafdkylqfwnucpighknhldklzhqnjbexbkankngqjtknkuurehypkkbltrydsfcvrelbtrrdmcqxwkqbtrsfbvrvmragweenippdiggukzrhlikfzekcabzmtbvrfzfpqwtyebspamymwirxmdbmhbbacytkxybnwulbwfsyrqkpadmohodorgqvejfbkhqgddjbidactktvqgmxwpnnvfiboqeaxujcxuehyelt...

output:

2

result:

ok single line: '2'

Test #36:

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

input:

wwjucpbthcaienbdkgxfwpptwgzxumytkhnnyoigsjowyrbixyqupfplnojkdjdpqqcognwywmxwdygbzwxoemctdndiwixmyccgpzhnlejpersdorsudwpijtqhbqvcsxkjyrykxjbcavfqmzkrvccgxsnakiceipngilsgwtkxqpncrawoeyvbskbdtghbvxjdkclhxveontsevoszopahackvktyhqhmbjykhvoxijpofgjguyjbynntxjrezbqckqmtmcqumgltmubiskktxzouiiakjrmvhbptdfqrl...

output:

2

result:

ok single line: '2'

Test #37:

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

input:

euajjxjlrejaxbyvxobwfcuruietgnnmhoxrlheelpfktfgqvhpbllufuyacooqxcoqpvxvimatfhzydipgtaaawbaarorosfhjcefmshfapgyuonajpcjmdmmucflvmugoyldsvismrqgffirxkcjqoxmrfxortuirilmdvepmxxuefnbppmhgmuzrtnknjsgrfswbxnpwkjarwcjoqqucktveigtrazlgsjjrxanjkpdirmykcsmpnivvqopqnayhjjyiknswdvewjdgnxvcldzivnxldxkkjtlrfylbbi...

output:

3

result:

ok single line: '3'

Test #38:

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

input:

ryqikpuwkabqupuqkxvqocdyzphkqsxksnsccobpqcflrzddzzundzneowphpmrhclmgznvppcahegkffgskfhouedbvsueufqaefyvvayeeeojlxdvcnjyrpbohvubcndisbepeetiikuvhzqlmbkfqnvxjqaldguxhapneiyousjbtzpgcbltohsxzvlebhbkjsynbydvsmzlnqrprfkfoffnaqtdzwpippxsnanfmorzekqxrddfikukanpbmejbugthgipuzgvfsndkqirasmmubbvpigqcmlluuaqvi...

output:

3

result:

ok single line: '3'

Test #39:

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

input:

qfwcuvpxrmdracykkzznjqjuohtsztqpaotwkitdxyuzcvmnwlafdmztvsounemptfmfqhipgfoiaaxwoadtocnjwbgmhsbczpjrxugdzvnbvnzlncfdgumcxsoeksjmhsdemkjnfzocmnobrvexpqcmlsqxkbjuupyizkwgjkkvaawtvctksvwfppdaqowmduveermpdxkfxizvkuffpekgtpglgcyjztqfmcvrbhxzqywcsbjjfwpalymrckddftjrxgkznhafhwkbxtkfpcfdcrwedbiiwtbuzmvovvud...

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0
Accepted
time: 17ms
memory: 41848kb

input:

qepycslklynhzkkruaucaztyrazoomsgqhevzrfmpuvpefiahffieyixajlovfuomylnsschmxytfhvmoawuyfryoeomkicyjnobfqktpjmusijgkfcjmtjdxyphirirgwunmfgdqvykdhsnouybnkemkvuuoemuaihopprfkrrpajfpddsspyfbtbwhfkdfsmtibmpmejbgsgvwmpqdnvfgwbpdluidgdnisfwwoxeigagsrxvfsanrdfuozfsikhqcomaelfnrhtlyqjdlltcpyyfzdzhohzqxntczypsf...

output:

3

result:

ok single line: '3'

Test #41:

score: 0
Accepted
time: 28ms
memory: 46104kb

input:

pjpylsynxoiagfroxaynqykxlarebqcqcuqpmocjemlnredrfbevzptnrmtuevngpdxcuznanznfdqwkucgttbilnbfrzuaoyxquzgumhktmcpxwudsngaytegmdaotammunsrbzbvldkkaepsuvusoayddbrxbfjysdpucqrpvdcxkrrenmwbmxgsyyrbfczyhoulglaeqcbautejhbkvatnargbwkdwrtscaffgwjhwfcbojebfguugndjlnokficjkkoqgazefchulnvstrnbesnrfbbmjgwtqmlymles...

output:

1

result:

ok single line: '1'

Test #42:

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

input:

bcqatarjdfzvabdynnqexqgutwlrxbtadjdyjujpzikbknbxcrezkkwdjhvgioinzlllhvagdmjncllecrembasmjnurddgeqrpymrgseqfgbskfjqunqmzzbwsgzykpqcpetwwzmchpwuwiksvbgwahstpttaljeaoxwmzkqgznayxlqsoxqogljwedwpoasezorabhhawjatwrnkogburmqxroniqhmsxfsypbznnzhjswwicxfvlvtdmilepzymfrlwumjhnqrgppqtmvpztiefqplhrktydguxsdhiwa...

output:

-1

result:

ok single line: '-1'

Test #43:

score: 0
Accepted
time: 8ms
memory: 40420kb

input:

vfitessxgeejhcxbbtxlnvvrhzfvngpkoxespwpxavgjafnbykolfjfnlkiatzkhwobnmqlpntynzlqxwgjdqosdacdtbncxedlqvyflreaqrrqpxbtprnsrqvnrlprpvefqclbvrcokveauhvkyiepacesnulcpphhtujonneyikaerxopfvfixjamflowcxevunljcqhmajqughjocqwbcynhldenaikwxxgbnpnqzdkhkvxomtrotexghbtklfikdolsgakhgwossmhehyudfrjovfygkjtpxgkfhumpt...

output:

2

result:

ok single line: '2'