QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#700365 | #5085. Palindrome Type | tamthegod# | AC ✓ | 28ms | 46104kb | C++23 | 1.3kb | 2024-11-02 12:48:56 | 2024-11-02 12:49:01 |
Judging History
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'