QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#697504#5085. Palindrome TypeAMATSUKAZE#WA 0ms3784kbC++201.0kb2024-11-01 14:26:282024-11-01 14:26:28

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 14:26:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3784kb
  • [2024-11-01 14:26:28]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'