QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#697504 | #5085. Palindrome Type | AMATSUKAZE# | WA | 0ms | 3784kb | C++20 | 1.0kb | 2024-11-01 14:26:28 | 2024-11-01 14:26:28 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define all(v) begin(v),end(v)
using namespace std;
using ll = long long;
using vl=vector<ll>;
using pll=pair<ll,ll>;
bool chmin(auto &a, auto b){ return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b){ return a < b ? a = b, 1 : 0; }
constexpr ll INF=1LL<<60;
int main(){
cin.tie(0)->sync_with_stdio(0);
string s;
cin>>s;
ll n=s.size();
string t=s;
reverse(all(t));
vl dp(7,INF);
rep(i,0,4) dp[i+3]=i;
rep(i,0,n){
vl DP(7,INF);
rep(j,0,7){
ll x=i+j-3;
if(x<0||x>=n) continue;
if(s[i]==t[x]) DP[j]=dp[j];
else{
if(j<6) chmin(DP[j],dp[j+1]+1);
if(j>0) chmin(DP[j],DP[j-1]+1);
}
}
dp=DP;
// rep(j,0,7){
// cout<<(dp[j]==INF?-1:dp[j])<<' ';
// }cout<<endl;
}
ll rs=dp[3];
if(rs>=8) rs=-1;
else rs>>=1;
cout<<rs<<endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
aababaa
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
abccbbab
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
acmicpc
output:
-1
result:
ok single line: '-1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
aabaa
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
abbaa
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
abcde
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
abcda
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
abaabba
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
bbbaaa
output:
3
result:
ok single line: '3'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
abbccba
output:
1
result:
ok single line: '1'
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3548kb
input:
abcabcb
output:
3
result:
wrong answer 1st lines differ - expected: '2', found: '3'