QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#743090 | #7955. Tandem Copy | yuto1115# | WA | 1ms | 4236kb | C++20 | 1.7kb | 2024-11-13 18:12:11 | 2024-11-13 18:12:12 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <cstring>
struct block {
char x, y;
int len, end;
};
const int N = 20005;
char s[N], t[N];
int n, m, t_block[N], s_block[N], dp[N];
std::vector<block> ss, tt;
void decomp(char *s, int n, int *s_block, std::vector<block> &blocks) {
for (int i = 0; i + 1 < n;) {
blocks.push_back({s[i], s[i + 1], 0});
++i;
int len = 1;
do {
s_block[i - 1] = blocks.size() - 1;
++len;
++i;
} while (i < n && s[i] == s[i - 2]);
blocks.back().len = len;
blocks.back().end = i;
--i;
}
}
int main() {
scanf("%s%s", s, t);
n = strlen(s);
for (int i = 0; t[i]; ++m) {
t[m] = t[i];
do {
++i;
} while (t[i] == t[i - 1]);
}
t[m] = 0;
decomp(s, n, s_block, ss);
decomp(t, m, t_block, tt);
dp[0] = -1;
int ans = 0;
for (int i = 1; i < n; ++i) {
bool ok = 1;
int j, k;
dp[i] = dp[i - 1];
if (tt.empty()) {
if (s[i] == t[0]) dp[i] = i;
}
else if (tt.size() == 1) {
if ((tt.back().x != s[i - 1] || tt.back().y != s[i]) && (tt.back().y != s[i - 1] || tt.back().x != s[i])) continue;
dp[i] = i - 1;
} else {
if (i == 1 || s[i] != s[i - 2]) {
if (tt.back().x != s[i - 1] || tt.back().y != s[i]) continue;
if (tt.size() > 1 && (i == 1)) continue;
if (s_block[i - 2] < (int)tt.size() - 2) continue;
for (j = (int)tt.size() - 2, k = s_block[i - 2]; j > 0 && ok; --j, --k) {
if (tt[j].x != ss[k].x || tt[j].y != ss[k].y) ok = 0;
if (tt[j].len < ss[k].len || (tt[j].len ^ ss[k].len) & 1) ok = 0;
}
if (ok) {
if (s[ss[k].end - 1] != t[tt[0].end - 1] && s[ss[k].end - 2] != t[tt[0].end - 2]) ok = 0;
}
} else ok = 0;
if (ok) {
dp[i] = ss[k].end - 2;
}
}
}
for (int i = 0; i < n; ++i) ans += dp[i] + 1;
printf("%d\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
ACGCG CCG
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
TATCGC TTCCG
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
ABCABC ABC
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
ABCABC ABCABC
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
FUSBX UUUUUUUUUU
output:
8
result:
ok single line: '8'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
IWN NNNNNNNNNN
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
RMRMRMRMRMRMRMRMRMRMR MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMR
output:
210
result:
ok single line: '210'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
TY YT
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
WZ ZW
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
SBSBSBSBSBSBSBSBSBSBSBSBSBSBSBSBSBSBWGVXPWAXMSBSB SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS...
output:
1121
result:
ok single line: '1121'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
TGJPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPXPX PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
897
result:
ok single line: '897'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
MKZOLDYLGAULULULUGASEAOZVIHNMRGKZQEIQYTGEMLBMAULULULULULULULPNERGKYZARPULULULULULAOZLQGYHULULULULZKYZUXEBVXZBULULULULULULULULULULULULULULULULDCEXCSTHQRULULULULULULULULULULULULULULULULULRDMPBDULULULUFVXWEMTULULULULULULULULULULULULULULULULULULULULCLULULULULULULULULULULULULULULULULULULULULULULULULULULU...
output:
46504613
result:
ok single line: '46504613'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
VEPZEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEMEM...
output:
43715406
result:
ok single line: '43715406'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
HKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKFBIAHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKIHKHKHKHKHKHKHKHKHKHKHKBHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHKHK...
output:
45393402
result:
ok single line: '45393402'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
ZHJDKBQNJPACACACACACACACACACACACACACACACACACACACACACACACEZACACACACACACACBLCRDQEACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACGUEKSAJOFACACACACACACACACACACACACACACACACACACACACACACKHUIOCNKXMKUOKACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACRACACACACACACACACACA...
output:
45452856
result:
ok single line: '45452856'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
CXQKRAVWKJFOHVJVMNSBGOEJZFAESPYDZCLUOHLBQEHIDLWQWQWQWQWQWQWQRETGMKPFZQWQWQWQWQWQWQWQWQWQWQWQWQWQWQWQSWLXQVWQWQWQWQWQWQWQWQVEHITSVRXBHEWCARSTKQZERXDNJTXGIHTBMCVYSKPSFYIDRGAIEVSTJGUBGMSQFXGWQFHBCTMGOWQWQWQWQWQWQWQPEYDLNUGDIOEKHRNSROPWQWQWQWQWQWQWQWQWQCMSPXODTIKOZYPFHROYFECRUJDWQWQWQWQWQWQWQWQWQWQJUWJK...
output:
49328004
result:
ok single line: '49328004'
Test #17:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
CBFKLKDEFBGHCEAMJIKGMLJFDKFIDJAKIADCHEJAMJBIFBJCEJCKDFLAFMEGDAMHLDCFGDBJDKLGIDCBMAFBMLFDJGAMLEAHBCIDLFJKCGHILCEDBLKIDMJDICBMFKLDKGLKMLFGKIDGHJIKJHBAJFMLJMEHGFEGAHBJLEBHKAJCKADEFGIEMGKCGMBEJKCFGAIMJBDGFHEMAELCDHCFJGAKEBJFHBDMKEMCJIKLGMCFJGDFLBACHECJMECIDGBKJHMEHILCKIBCLIFMHJFDGAILEBGIAJIFCILFJBLFALGB...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
JIDABCASN ABCBABCBC
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
ASFJABCSFN ABCABC
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
ELUNVXDGQHAYMVWAYBQUJIMOFNOVPTALPHTWCPDMALKAZEAPXFMZCTLKHFIYPUOYKIVLNGHTXSJNIHZURWNYNXBMWOVZYXAQDKFWTHCYVQNFMNIQRFWKTQYHAVJOXNMPTIRWLJXERAWFSZKVOWTNXOTXSTWIGNCEKWDEADLSWHCQDPECUXEKAFEHPKHLTHPFYLUBXGMKENZTOQZKAESFNIQAKUVWPNQAPEHAVIWFAOIXMBPJITYOLTKYGAWKBDOZJUFOVCPGDFZLFQIGEBDEMNUPYEKWSCGDOUWEOJXMAHGZ...
output:
0
result:
ok single line: '0'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
QAUFICKQDARDZBSWEMXFDPAUJVBDHVTAZDJRMXVNQYBWJLOSONYGXZNKURCGHMXFGZSQIGSRMPSDJGLFUWZJVMDAGUFOXIFHCTWLMLTSMJLOSCLYEYEXZKBEVMORHAGMKCMPIBZXCMNVOEXBJOYBHMVZHBYMVBFLNZPSDZBUEOCZJHZEAUZREVNLIDNHCYBJVBGPSVKSNHTUONLREOIPVTRXIZAYRAPZVYENZVXYIWZLQOVTGZPUAMBSWFVIUHJNACLOFVGNSKPMTSYLVTUIPWKVJYLWKGWZBGCEBVDYTVYI...
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
BIUBEMOYSEHTDAYBGSTIEGZAFLQFRKXZHKMLIZORXMYPRIPZVSBPVJYHMFBKVIFXAYFJQCPEGPERASKTJFNYVXNXALJGSABVIEURYVHBVEIAZUXSPANGABQRZHTKQJBTEWLGSTAMEFSZHBZOFDWPXMAZYDPIWXSIMYELONUAJXHBZWSFKEABYQKFRIWYVIFQBLSQJKRTLONRQBJARCKJTKGFIWFRDNYICDQXLIJUVXZNJKGQTEUXGHAEYHWBXYCOSMTPIXRYKIGQLMJCYDIKSPZMCSEHWRHAXEQCZYHXOSWU...
output:
0
result:
ok single line: '0'
Test #23:
score: 0
Accepted
time: 1ms
memory: 4236kb
input:
TGZBZAEQDTWERZFYHZPTVHCLFIVBCOTZAKVSXYUXHLCRIDGLJEWULEVJEZSXUCPXBPCVLACGKCLNRPLVPUWKSOWXREVIHXDSQWCLYEBHOMDYHGQVZADJOSQMBUSKGVEQOMKLBCWNUGOLFZXEPRCZKWJXEZVOWNGVEDQYJIECTMQHXOVPYZDUBZMFBJWZHMAVMWZPFUYXVKLERIPRVMWYUSOZFYAKDZMQDEUSGMVSDHBYFIPOGKIAYHRTBYPGOXMGYSRHWRIZBIZWQITLFKYRWASGAPLUFMIUZJTRVYJLZCQV...
output:
0
result:
ok single line: '0'
Test #24:
score: 0
Accepted
time: 1ms
memory: 4076kb
input:
AIEYDRNKWSEGPLDXVHXFMSJGUQFVNRXTQPVQZHWEHUBVAUPUTCQJYTEBJWEULSDIPVQPNGIODAZRSUQFYEMZEQDALGHMNLETNXTNECTOQGIEVAJFPATYDXIHEGAPMRQUTGCNUTJHFSZJDIUFXHBEMWHDCIYJUGYTHOCEZRTHXWHEWFIVONEGUMKGIENRALWBJLSQAYOFZLBXMAOXPIMTSJEFZEGNMQSPUCZHMRDNVPKJVATROZAQGFOWCTUVKOMVWDAXLRMOZHNEAHUOKEDSYJRAWQLMRUDQCXOTBQOXGRBG...
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
ZJPVDHIXEZCWVXWOZYEILQHRPRQZORZQBLIXHCKPGJYIZDBZDENDLPHYRMAONHOAKTHMTKHJBFJYRKQTHLZHTPKJQSXZEHRQGBPRWDMFHWTJZTJCEYLZAJCMEKXHJORTJMFHNAEMJBOLTUYXVLXCZFUNRIGVESCBHSVGUXRMUKIRCAXCIYSCLYCBADRGTQGZTWDBMOEWHPFRXPISNECTFVQRJZUJRGLYMOWHFZDXAMHTCRLXPOMKCXSVGKHJVLDRAHDYMWHURFOJCYPLVYLVUMAZDEHCNBOQWBYIPMDYXUTO...
output:
0
result:
ok single line: '0'
Test #26:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
QKNDNBUGVUTWQVNETHRWEUWFHJEYGKLAHKSALTHQCTSPFOUMTGWSGCLYIQDPERLHMXZQIAFBVGDQRJWPCFTRQSNRYVPRYCHQUBCYHRAMQXFBXMVXCPXVOIFUYZVOAFMARDSEQPENUAEQWVNBMVJXTBKYTEMCSOPHSRDMWZPQLWVLIAPWNRVQCNBEXGWZXOFRKBJFCUQWNCRURAQLFPSXBSUOFQCRGCVGQYDHXBESHMZJOTLXAUOECHBOEDHRIJRAHELBYXWSQGPXITSRKDNFXSTZYXHSGIPWAZMDUZIXVJGU...
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 4072kb
input:
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
0
result:
ok single line: '0'
Test #28:
score: -100
Wrong Answer
time: 1ms
memory: 4080kb
input:
CBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
19998
result:
wrong answer 1st lines differ - expected: '0', found: '19998'