QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#302459 | #7955. Tandem Copy | PetroTarnavskyi# | WA | 2ms | 3612kb | C++20 | 1.8kb | 2024-01-10 21:36:22 | 2024-01-10 21:36:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
VI prefixFunction(const string& s)
{
int n = SZ(s);
VI p(n);
p[0] = 0;
FOR (i, 1, n)
{
int j = p[i - 1];
while(j != 0 && s[i] != s[j])
j = p[j - 1];
if (s[i] == s[j]) j++;
p[i] = j;
}
return p;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
string s, t;
cin >> s >> t;
string okt = "";
FOR(i, 0, SZ(t))
{
if(SZ(okt) > 0 && okt.back() == t[i])
continue;
okt += t[i];
}
t = okt;
okt = "";
FOR(i, 0, SZ(t))
{
if(SZ(okt) > 1 && i + 1 < SZ(t) && okt[SZ(okt) - 2] == t[i] && okt.back() == t[i + 1])
{
i++;
continue;
}
okt += t[i];
}
if(SZ(okt) > 2 && okt[SZ(okt) - 3] == okt.back())
okt.pop_back();
if(SZ(okt) > 2 && okt[0] == okt[2])
okt = okt.substr(1, SZ(okt) - 1);
t = okt;
if(SZ(t) == 2)
{
LL ans = 0;
int l = -1;
FOR(i, 0, SZ(s) - 1)
{
bool ok = (s[i] == t[0] && s[i + 1] == t[1]);
ok |= (s[i] == t[1] && s[i + 1] == t[0]);
if(!ok)
continue;
ans += (SZ(s) - i - 1) * (i - l);
l = i;
}
cout << ans << endl;
return 0;
}
auto p = prefixFunction(t + "#" + s);
LL ans = 0;
int l = SZ(t);
FOR(i, SZ(t) + 1, SZ(p))
{
if(p[i] == SZ(t))
{
ans += (SZ(p) - i) * (LL) (i - SZ(t) + 1 - l);
l = i - SZ(t) + 1;
}
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3540kb
input:
ACGCG CCG
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
TATCGC TTCCG
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
ABCABC ABC
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
ABCABC ABCABC
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
FUSBX UUUUUUUUUU
output:
8
result:
ok single line: '8'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
IWN NNNNNNNNNN
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
RMRMRMRMRMRMRMRMRMRMR MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMR
output:
210
result:
ok single line: '210'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
TY YT
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
WZ ZW
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
SBSBSBSBSBSBSBSBSBSBSBSBSBSBSBSBSBSBWGVXPWAXMSBSB SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...
output:
1121
result:
ok single line: '1121'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
TGJPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPX PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
897
result:
ok single line: '897'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
MKZOLDYLGAULULULUGASEAOZVIHNMRGKZQEIQYTGEMLBMAULULULULULULULPNERGKYZARPULULULULULAOZLQGYHULULULULZKYZUXEBVXZBULULULULULULULULULULULULULULULULDCEXCSTHQRULULULULULULULULULULULULULULULULULRDMPBDULULULUFVXWEMTULULULULULULULULULULULULULULULULULULULULCLULULULULULULULULULULULULULULULULULULULULULULULULULULU...
output:
46504613
result:
ok single line: '46504613'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
VEPZEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEM...
output:
43715406
result:
ok single line: '43715406'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
HKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKFBIAHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKIHKHKHKHKHKHKHKHKHKHKHKBHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHK...
output:
45393402
result:
ok single line: '45393402'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
ZHJDKBQNJPACACACACACACACACACACACACACACACACACACACACACACACEZACACACACACACACBLCRDQEACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACGUEKSAJOFACACACACACACACACACACACACACACACACACACACACACACKHUIOCNKXMKUOKACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACRACACACACACACACACACA...
output:
45452856
result:
ok single line: '45452856'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
CXQKRAVWKJFOHVJVMNSBGOEJZFAESPYDZCLUOHLBQEHIDLWQWQWQWQWQWQWQRETGMKPFZQWQWQWQWQWQWQWQWQWQWQWQWQWQWQWQSWLXQVWQWQWQWQWQWQWQWQVEHITSVRXBHEWCARSTKQZERXDNJTXGIHTBMCVYSKPSFYIDRGAIEVSTJGUBGMSQFXGWQFHBCTMGOWQWQWQWQWQWQWQPEYDLNUGDIOEKHRNSROPWQWQWQWQWQWQWQWQWQCMSPXODTIKOZYPFHROYFECRUJDWQWQWQWQWQWQWQWQWQWQJUWJK...
output:
49328004
result:
ok single line: '49328004'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
CBFKLKDEFBGHCEAMJIKGMLJFDKFIDJAKIADCHEJAMJBIFBJCEJCKDFLAFMEGDAMHLDCFGDBJDKLGIDCBMAFBMLFDJGAMLEAHBCIDLFJKCGHILCEDBLKIDMJDICBMFKLDKGLKMLFGKIDGHJIKJHBAJFMLJMEHGFEGAHBJLEBHKAJCKADEFGIEMGKCGMBEJKCFGAIMJBDGFHEMAELCDHCFJGAKEBJFHBDMKEMCJIKLGMCFJGDFLBACHECJMECIDGBKJHMEHILCKIBCLIFMHJFDGAILEBGIAJIFCILFJBLFALGB...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
JIDABCASN ABCBABCBC
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
ASFJABCSFN ABCABC
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
ELUNVXDGQHAYMVWAYBQUJIMOFNOVPTALPHTWCPDMALKAZEAPXFMZCTLKHFIYPUOYKIVLNGHTXSJNIHZURWNYNXBMWOVZYXAQDKFWTHCYVQNFMNIQRFWKTQYHAVJOXNMPTIRWLJXERAWFSZKVOWTNXOTXSTWIGNCEKWDEADLSWHCQDPECUXEKAFEHPKHLTHPFYLUBXGMKENZTOQZKAESFNIQAKUVWPNQAPEHAVIWFAOIXMBPJITYOLTKYGAWKBDOZJUFOVCPGDFZLFQIGEBDEMNUPYEKWSCGDOUWEOJXMAHGZ...
output:
0
result:
ok single line: '0'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
QAUFICKQDARDZBSWEMXFDPAUJVBDHVTAZDJRMXVNQYBWJLOSONYGXZNKURCGHMXFGZSQIGSRMPSDJGLFUWZJVMDAGUFOXIFHCTWLMLTSMJLOSCLYEYEXZKBEVMORHAGMKCMPIBZXCMNVOEXBJOYBHMVZHBYMVBFLNZPSDZBUEOCZJHZEAUZREVNLIDNHCYBJVBGPSVKSNHTUONLREOIPVTRXIZAYRAPZVYENZVXYIWZLQOVTGZPUAMBSWFVIUHJNACLOFVGNSKPMTSYLVTUIPWKVJYLWKGWZBGCEBVDYTVYI...
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
BIUBEMOYSEHTDAYBGSTIEGZAFLQFRKXZHKMLIZORXMYPRIPZVSBPVJYHMFBKVIFXAYFJQCPEGPERASKTJFNYVXNXALJGSABVIEURYVHBVEIAZUXSPANGABQRZHTKQJBTEWLGSTAMEFSZHBZOFDWPXMAZYDPIWXSIMYELONUAJXHBZWSFKEABYQKFRIWYVIFQBLSQJKRTLONRQBJARCKJTKGFIWFRDNYICDQXLIJUVXZNJKGQTEUXGHAEYHWBXYCOSMTPIXRYKIGQLMJCYDIKSPZMCSEHWRHAXEQCZYHXOSWU...
output:
0
result:
ok single line: '0'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
TGZBZAEQDTWERZFYHZPTVHCLFIVBCOTZAKVSXYUXHLCRIDGLJEWULEVJEZSXUCPXBPCVLACGKCLNRPLVPUWKSOWXREVIHXDSQWCLYEBHOMDYHGQVZADJOSQMBUSKGVEQOMKLBCWNUGOLFZXEPRCZKWJXEZVOWNGVEDQYJIECTMQHXOVPYZDUBZMFBJWZHMAVMWZPFUYXVKLERIPRVMWYUSOZFYAKDZMQDEUSGMVSDHBYFIPOGKIAYHRTBYPGOXMGYSRHWRIZBIZWQITLFKYRWASGAPLUFMIUZJTRVYJLZCQV...
output:
0
result:
ok single line: '0'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
AIEYDRNKWSEGPLDXVHXFMSJGUQFVNRXTQPVQZHWEHUBVAUPUTCQJYTEBJWEULSDIPVQPNGIODAZRSUQFYEMZEQDALGHMNLETNXTNECTOQGIEVAJFPATYDXIHEGAPMRQUTGCNUTJHFSZJDIUFXHBEMWHDCIYJUGYTHOCEZRTHXWHEWFIVONEGUMKGIENRALWBJLSQAYOFZLBXMAOXPIMTSJEFZEGNMQSPUCZHMRDNVPKJVATROZAQGFOWCTUVKOMVWDAXLRMOZHNEAHUOKEDSYJRAWQLMRUDQCXOTBQOXGRBG...
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
ZJPVDHIXEZCWVXWOZYEILQHRPRQZORZQBLIXHCKPGJYIZDBZDENDLPHYRMAONHOAKTHMTKHJBFJYRKQTHLZHTPKJQSXZEHRQGBPRWDMFHWTJZTJCEYLZAJCMEKXHJORTJMFHNAEMJBOLTUYXVLXCZFUNRIGVESCBHSVGUXRMUKIRCAXCIYSCLYCBADRGTQGZTWDBMOEWHPFRXPISNECTFVQRJZUJRGLYMOWHFZDXAMHTCRLXPOMKCXSVGKHJVLDRAHDYMWHURFOJCYPLVYLVUMAZDEHCNBOQWBYIPMDYXUTO...
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
QKNDNBUGVUTWQVNETHRWEUWFHJEYGKLAHKSALTHQCTSPFOUMTGWSGCLYIQDPERLHMXZQIAFBVGDQRJWPCFTRQSNRYVPRYCHQUBCYHRAMQXFBXMVXCPXVOIFUYZVOAFMARDSEQPENUAEQWVNBMVJXTBKYTEMCSOPHSRDMWZPQLWVLIAPWNRVQCNBEXGWZXOFRKBJFCUQWNCRURAQLFPSXBSUOFQCRGCVGQYDHXBESHMZJOTLXAUOECHBOEDHRIJRAHELBYXWSQGPXITSRKDNFXSTZYXHSGIPWAZMDUZIXVJGU...
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
0
result:
ok single line: '0'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
CBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
0
result:
ok single line: '0'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
0
result:
ok single line: '0'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
INBHJGLCDJGRSNWHTXFEGIAWVWXROMSYXZTFCBHWTIXCBZEJZFGPZKAXTJFQVDTANSJCETHIPGHFELUHBTZRIOBTMLYMRCQDVNCAUIXQTZKAGMPWLUVJFVAZMRXAOSDYJHYKISJTSMTQYCIFTNHECWDYIWGEVZMLBMUJYOKALXYVUTWVBKDBRIUJGTKMUFHWZOCPNIYONVYHVRGPFCWFJQKDLRXFOGSOXEZBIZEWLNROMXZWIFHDCHFEDMUITXCPLTWQCBLXFJQUZSOHXKLFRPTYPNODIXMSUXNSBQHKAWCJ...
output:
0
result:
ok single line: '0'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
TFQCDUYXLOYHPUIHIKATDYXRVKLWDBGSHPQTVSBKHONRAKTDJSERAIODSCQOEKCTHAGXRVPHEMOTUBETNUCWDHEOWJPMGKTZCPWVPGRBTWISZHPQABQULBKDQURQHRCMPEKHOLGTQNHFXWPXARBSJNLEPYZVEJSYFVYAQIULITNEFKLGMLWXCVGJSBTNRBQTXOACDVHYLKWZVFAJDNLSBEOWPTZSOGVTJACIUNZJTANFIGQMFLMHSATMPXEOVXLGMOEUZYHNTHVKOMGLJRSMVXQYVOMJEHZGNJVNOGBUCKQF...
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
QWKDETMOTCFHWAKLRYCJLQBHMGXEBFEYIFIQYKOURSTXEBXUETDXAQBYKSJIZKWMSIAPSYZQICSJBPSAKUPEFJLMODTHSNBIHLKNGMRQNYLFTVPYUQDPUVINLIMRGSWULQDYQVKRDWHAVQARIWXPFRBFZDFPZVFMUFDRIPSWEQYEQGOXHEOGHEGDRAGHTUYMQJHKGREXHQATPHWGAHYIVAFIQHOPYSRENZKAHBCFVPZKWPIGNIYOUXFQKZURTKIHFOJBMHOLFDWOEJHDVLWZEPDVMCSPWKJEXLEKGBUCOZDI...
output:
0
result:
ok single line: '0'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
PMONBRZUXLXOMICDOYGCDRILAPJCUISVFCWUXHDUBXTVPGVKAUGYBDRBMXNDWHMSRZFMRXSVDSNZQXBMDUNEYZDWOKAERTSMEYJCLFWYLNHCOQKDLTJPMNCJWLZGKVHERNZQYSFTQGSXDYQRWSDFMRHCFEYHEZBENBQRYMPXDWIBRFGRIGMPWNISLDIYBKIJKTSVJRHZUOWZONHAXTDZIHSABHFXYWLJTADJGREOVSJYTAIUSAJPQUFNXBZVTWONZUODJBNGXFDAODBJGHRQXLMBWTUXFEVZWLJPINSBMGTJ...
output:
0
result:
ok single line: '0'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
IGOCPESZSKCGJBLHDFKLNBENRFXNQAYFVLNWPTDYFANZMCARIMZKEPWQTYCPJILYNOVJSFEZWOBNJKGSEGFJIQOHUYTHXVKUAISVPRMUXAKXZVJWQMFNWLAQENGTORCLDTRBNZLENSKQFLGMJHWBIUMAQJCUTWRMXYKLXWLSNDSVITYZHCBYGJSRKHPUBQCZSIMEROWVYLAQNLQOYEMGSLTNQETDXZWEQUSMCGALKITMKOIFDQRWYCUTWJVIMSTCOADHIJPLWRKXHGNOMSGPXFADBMZTILHROCSARTLPDRFC...
output:
0
result:
ok single line: '0'
Test #35:
score: -100
Wrong Answer
time: 0ms
memory: 3512kb
input:
UNINININININIUNININIUNINININININININIU NINININIUNININIU
output:
0
result:
wrong answer 1st lines differ - expected: '216', found: '0'