QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333524 | #5577. Alchemy | joelgun14# | WA | 0ms | 3640kb | C++14 | 1.6kb | 2024-02-20 05:28:36 | 2024-02-20 05:28:37 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x.begin(), x.end())
using namespace std;
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
const int N = 2e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
int main() {
string s;
cin >> s;
bool ans[s.size() / 2];
memset(ans, 0, sizeof(ans));
for(int i = 0; i < s.size() / 2; ++i) {
if(s[i] != s[s.size() - i - 1]) {
ans[i] = 1;
}
}
reverse(ans, ans + s.size() / 2);
// 0 -> wrong
// 1 -> correct
int dp[s.size() / 2][2];
memset(dp, -1, sizeof(dp));
if(ans[0]) {
// wrong
dp[0][1] = 1;
dp[0][0] = 0;
}
else {
// corect
dp[0][1] = 0;
dp[0][0] = 1;
}
for(int i = 1; i < s.size() / 2; ++i) {
// toggle prev wrong
dp[i][0] = dp[i - 1][0] + 1;
dp[i][1] = dp[i - 1][0] + 1;
// not toggle prev correct
if(ans[i]) {
// current wrong
dp[i][0] = min(dp[i][0], dp[i - 1][1]);
dp[i][1] = min(dp[i][1], dp[i - 1][1] + 2);
}
else {
dp[i][1] = min(dp[i][1], dp[i - 1][1]);
dp[i][0] = min(dp[i][0], dp[i - 1][1] + 2);
}
}
cout << dp[s.size() / 2 - 1][1] << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
ioi
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
noi
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
ctsc
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
fool
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
vetted
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
aa
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
ic
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
tlffohemdcncrfrxaqsbzcoyodvbxmhqukvfpahnakexcmacqa
output:
12
result:
ok single line: '12'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
qrgld
output:
1
result:
ok single line: '1'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3540kb
input:
ejyfprguvwrnrsrykyrotmdjuzroohvlxqhvyeukkvmshtpczyyecpzhsqvkxueqvhlxldhofrzcjdhtotykgrsdnrnvuyrphyjy
output:
18
result:
wrong answer 1st lines differ - expected: '26', found: '18'