Task: | Palindrome |
Sender: | Kyynel ;_; |
Submission time: | 2016-09-20 17:50:41 +0300 |
Language: | C++ |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.54 s | details |
#2 | ACCEPTED | 0.53 s | details |
#3 | ACCEPTED | 0.42 s | details |
#4 | WRONG ANSWER | 0.42 s | details |
#5 | ACCEPTED | 0.42 s | details |
#6 | ACCEPTED | 0.43 s | details |
#7 | ACCEPTED | 0.46 s | details |
#8 | WRONG ANSWER | 0.54 s | details |
#9 | ACCEPTED | 0.41 s | details |
#10 | ACCEPTED | 0.43 s | details |
#11 | ACCEPTED | 0.42 s | details |
#12 | ACCEPTED | 0.46 s | details |
#13 | ACCEPTED | 0.54 s | details |
#14 | ACCEPTED | 0.54 s | details |
#15 | ACCEPTED | 0.47 s | details |
#16 | WRONG ANSWER | 0.57 s | details |
#17 | ACCEPTED | 0.59 s | details |
#18 | ACCEPTED | 0.41 s | details |
#19 | ACCEPTED | 0.58 s | details |
#20 | WRONG ANSWER | 0.43 s | details |
#21 | ACCEPTED | 0.44 s | details |
#22 | ACCEPTED | 0.45 s | details |
#23 | ACCEPTED | 0.42 s | details |
#24 | ACCEPTED | 0.68 s | details |
#25 | ACCEPTED | 0.49 s | details |
#26 | ACCEPTED | 0.39 s | details |
#27 | ACCEPTED | 0.43 s | details |
#28 | WRONG ANSWER | 0.62 s | details |
#29 | ACCEPTED | 0.45 s | details |
#30 | ACCEPTED | 0.43 s | details |
Compiler report
input/code.cpp: In function 'int edit(std::string, std::string)': input/code.cpp:9:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int y = 0; y <= s.length(); y++) { ^ input/code.cpp:10:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for (int x = 0; x <= t.length(); x++) { ^ input/code.cpp: In function 'bool ok(int)': input/code.cpp:28:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (i + 1 >= s.length()) return false; ^ input/code.cpp: In function 'bool ok2(int)': input/code.cpp:45:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (i + 2 >= s.length()) return false; ^ input/code.cpp: In function 'int main()': input/code.cpp:61:29: warning: comparison between signed and unsigned integer...
Code
#include <bits/stdc++.h> #define ll long long #define N (1<<17) using namespace std; int edit (string s, string t) { int dp[s.length() + 1][t.length() + 1]; for (int y = 0; y <= s.length(); y++) { for (int x = 0; x <= t.length(); x++) { if (x == 0) dp[y][0] = y; else if (y == 0) dp[0][x] = x; else dp[y][x] = min(min(dp[y][x - 1] + 1, dp[y - 1][x] + 1), dp[y - 1][x - 1] + (s[y - 1] == t[x - 1] ? 0 : 1)); } } return dp[s.length()][t.length()]; } int ans = 999999999; string s; bool ok (int i) { string x = s.substr(0, i); string y = s.substr(i, s.length() - i); reverse(y.begin(), y.end()); int a = edit(x, y); ans = min(ans, a); if (((int)s.length()) - i - 1 < 0) return false; if (i + 1 >= s.length()) return false; x = s.substr(0, i + 1); y = s.substr(i + 1, s.length() - i - 1); reverse(y.begin(), y.end()); int b = edit(x, y); ans = min(min(a, b), ans); return b <= a; } bool ok2 (int i) { string x = s.substr(0, i); string y = s.substr(i + 1, s.length() - i - 1); reverse(y.begin(), y.end()); int a = edit(x, y); ans = min(ans, a); if (((int)s.length()) - i - 2 < 0) return false; if (i + 2 >= s.length()) return false; x = s.substr(0, i + 1); y = s.substr(i + 2, ((int)s.length()) - i - 2); reverse(y.begin(), y.end()); int b = edit(x, y); ans = min(min(a, b), ans); return b <= a; } int main () { cin>>s; if (s.length() == 1) cout<<0<<endl, exit(0); int k = s.length(); int i = 0; for (; k >= 1; k /= 2) { while (i + k < s.length() && ok(i + k)) i += k; } int j = 0; k = s.length(); for (; k >= 1; k /= 2) { while (j + k < s.length() && ok2(j + k)) j += k; } for (int i2 = max(0, i - 5); i2 < min(i + 6, (int)s.length()); i2++) ok(i2); for (int j2 = max(0, j - 5); j2 < min(j + 6, (int)s.length()); j2++) ok2(j2); cout<<ans<<endl; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
ulfoeirkeoqdqodoogghreatbunekn... |
correct output |
---|
322 |
user output |
---|
322 |
Test 2
Verdict: ACCEPTED
input |
---|
pdloqnpaoipdormtocrkbugqkutggo... |
correct output |
---|
42 |
user output |
---|
42 |
Test 3
Verdict: ACCEPTED
input |
---|
nsjeeqtgbhihbqnrkjqesndoqpsupm... |
correct output |
---|
6 |
user output |
---|
6 |
Test 4
Verdict: WRONG ANSWER
input |
---|
cbdabbabdadbddccdabbddbbabdbcb... |
correct output |
---|
520 |
user output |
---|
522 |
Test 5
Verdict: ACCEPTED
input |
---|
qufflsdamkhaqfstkpmggbiscqahmb... |
correct output |
---|
332 |
user output |
---|
332 |
Test 6
Verdict: ACCEPTED
input |
---|
metqijcfsonpgtjkgfnbkkcmhfdidr... |
correct output |
---|
52 |
user output |
---|
52 |
Test 7
Verdict: ACCEPTED
input |
---|
gjctsgogicncablbpicjhhhtumcqcr... |
correct output |
---|
7 |
user output |
---|
7 |
Test 8
Verdict: WRONG ANSWER
input |
---|
bcdaccdaaaddbddbcbabccbabbcadd... |
correct output |
---|
517 |
user output |
---|
521 |
Test 9
Verdict: ACCEPTED
input |
---|
ljqskggebsriqfcrbaseostkbtufpk... |
correct output |
---|
323 |
user output |
---|
323 |
Test 10
Verdict: ACCEPTED
input |
---|
opthatefgdoqcnelkocdpiekdalblk... |
correct output |
---|
43 |
user output |
---|
43 |
Test 11
Verdict: ACCEPTED
input |
---|
tsifskqoacandopustasbcprqqgubc... |
correct output |
---|
9 |
user output |
---|
9 |
Test 12
Verdict: ACCEPTED
input |
---|
dcdcddcaccccccbddabadacadaadad... |
correct output |
---|
519 |
user output |
---|
519 |
Test 13
Verdict: ACCEPTED
input |
---|
psmqpkpdbflqsnummddslbbmqlbttl... |
correct output |
---|
344 |
user output |
---|
344 |
Test 14
Verdict: ACCEPTED
input |
---|
kfbicrmensbkppfnechdgaangnekra... |
correct output |
---|
47 |
user output |
---|
47 |
Test 15
Verdict: ACCEPTED
input |
---|
utmicheffpsumjmdmlltfkauerouou... |
correct output |
---|
7 |
user output |
---|
7 |
Test 16
Verdict: WRONG ANSWER
input |
---|
aadcbccaddbbddaacdacbadcccccab... |
correct output |
---|
513 |
user output |
---|
519 |
Test 17
Verdict: ACCEPTED
input |
---|
knousbhjpartmqrddgtuilrqmptfbm... |
correct output |
---|
347 |
user output |
---|
347 |
Test 18
Verdict: ACCEPTED
input |
---|
mialfaqdecpampccjljbtfcsobdumg... |
correct output |
---|
50 |
user output |
---|
50 |
Test 19
Verdict: ACCEPTED
input |
---|
tbolpoikroedjdrjqboqptktnqfulo... |
correct output |
---|
15 |
user output |
---|
15 |
Test 20
Verdict: WRONG ANSWER
input |
---|
babbbabcacbbbdcaacddadaaadccdc... |
correct output |
---|
521 |
user output |
---|
529 |
Test 21
Verdict: ACCEPTED
input |
---|
oqbbmemeheigflklkicqdlriifijfp... |
correct output |
---|
350 |
user output |
---|
350 |
Test 22
Verdict: ACCEPTED
input |
---|
iscgirlmkcdgisciganitjdugeoegb... |
correct output |
---|
45 |
user output |
---|
45 |
Test 23
Verdict: ACCEPTED
input |
---|
nrlifhnrkorbihsosdibeaapnbcmnp... |
correct output |
---|
10 |
user output |
---|
10 |
Test 24
Verdict: ACCEPTED
input |
---|
ddbdcacbacadaaaaddcaadbdcabbba... |
correct output |
---|
524 |
user output |
---|
524 |
Test 25
Verdict: ACCEPTED
input |
---|
pskpisphqttuafltbrgiliehohrdre... |
correct output |
---|
301 |
user output |
---|
301 |
Test 26
Verdict: ACCEPTED
input |
---|
qlmpbmdcjgiibjdggepnjgdqddrjgu... |
correct output |
---|
42 |
user output |
---|
42 |
Test 27
Verdict: ACCEPTED
input |
---|
kmemgrjpooulrgoofbejhtfnsdpfnl... |
correct output |
---|
5 |
user output |
---|
5 |
Test 28
Verdict: WRONG ANSWER
input |
---|
dbadbacabbaabccdbcacdadbaddcca... |
correct output |
---|
523 |
user output |
---|
524 |
Test 29
Verdict: ACCEPTED
input |
---|
riucascnslqgplsknhpmccgqenhpni... |
correct output |
---|
357 |
user output |
---|
357 |
Test 30
Verdict: ACCEPTED
input |
---|
dedhqdrbrorasgunkdtdsujciuaqbu... |
correct output |
---|
48 |
user output |
---|
48 |