QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#317722#5577. AlchemyLi__WA 0ms3880kbC++20782b2024-01-29 16:06:532024-01-29 16:06:54

Judging History

This is the latest submission verdict.

  • [2024-01-29 16:06:54]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3880kb
  • [2024-01-29 16:06:53]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int inf = 1100;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);	
	
	string s;
	cin>>s;

	int n=s.size();
	s=" "+s;

	vector dp(n+1,vector<i64>(2,inf));

	dp[1][0]=0;
	int m=(n+1)/2;
	if(n%2!=0){
		s.erase(m,1);
		m--;
		n--;
	}
	for(int i=1;i<=m;i++){
		if(s[i]==s[n-i+1]) dp[i+1][0]=min(dp[i+1][0],dp[i][0]);
		else{
			dp[i+1][1]=min(dp[i+1][1],dp[i][0]+1);
			if(i!=m) dp[i+2][0]=min(dp[i+2][0],dp[i][0]+2);
		}
		if(s[i]!=s[n-i+1]) dp[i+1][0]=min(dp[i+1][0],dp[i][1]);
		else{
			dp[i+1][1]=min(dp[i+1][1],dp[i][0]+1);
			if(i!=m) dp[i+2][0]=min(dp[i+2][0],dp[i][0]+2);
		}
	}
	i64 ans=min(dp[m+1][0],dp[m+1][1]);
	cout<<ans<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

input:

ioi

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

noi

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

ctsc

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

fool

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

vetted

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

aa

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

ic

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

tlffohemdcncrfrxaqsbzcoyodvbxmhqukvfpahnakexcmacqa

output:

12

result:

ok single line: '12'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

qrgld

output:

1

result:

ok single line: '1'

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 3880kb

input:

ejyfprguvwrnrsrykyrotmdjuzroohvlxqhvyeukkvmshtpczyyecpzhsqvkxueqvhlxldhofrzcjdhtotykgrsdnrnvuyrphyjy

output:

18

result:

wrong answer 1st lines differ - expected: '26', found: '18'