QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718303#7624. Mystery of PrimeEMTzWA 4ms14120kbC++202.2kb2024-11-06 20:13:202024-11-06 20:13:20

Judging History

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

  • [2024-11-06 20:13:20]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:14120kb
  • [2024-11-06 20:13:20]
  • 提交

answer

#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
using namespace std;
typedef pair<int,int>PII;
typedef pair<int,PII>PPI;
typedef array<int,3>ar;
const int N=2e5+7;
const int N1=1e9+9;
const int M=998244353;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 rng(time(0));
const int M1=19260817;
const int base=233;
const int base1=131;
const int INF = 0x3f3f3f3f;
int pr[N],st[N];
int k;
int a[N],dp[N][3][4];
// 0 0 不变 偶
//0 1 不变 奇
//1 0 变 偶
//1 1 变 奇
//1 2 变 1
void prs()
{
	for(int i=2;i<N;i++)
	{
		if(st[i]==0) pr[++k]=i;
		for(int j=1;j<=k&&pr[j]*i<N;j++)
		{
			st[pr[j]*i]=1;
			if(i%pr[j]==0) break;
		} 
	}
}
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	memset(dp,INF,sizeof dp);
	if(a[1]==1)
	{
		dp[1][0][2]=0;
	}
	else if(a[1]%2==0) dp[1][0][0]=0;
	else dp[1][0][1]=0;
	for(int i=0;i<=1;i++){
		for(int j=0;j<=2;j++)
		{
			dp[0][i][j]=0;
		}
	}
	for(int i=2;i<=n;i++)
	{
		int o=a[i]%2;
		int o1=a[i-1]%2;
		if(a[i]==1) o=2;
		if(a[i-1]==1) o1=2;
		if(st[a[i]+a[i-1]]==0)
		{
			dp[i][0][o]=min(dp[i][0][o],dp[i-1][0][o1]);
		}
		dp[i][0][o]=min(dp[i][0][o],min(dp[i-2][0][o],dp[i-2][1][o])+1);
		if(st[a[i]+1]==0)
		{
			dp[i][0][o]=min(dp[i][0][o],min(dp[i-2][0][2],dp[i-2][1][2])+1);
		}
		if(a[i]==1)
		{
			if(st[a[i-1]+1]==0)dp[i][0][2]=min(dp[i][0][2],min(dp[i-1][0][0],dp[i-1][0][2]));
			dp[i][0][2]=min(dp[i][0][2],min(dp[i-2][0][2],dp[i-2][1][2])+1);
			dp[i][0][2]=min(dp[i][0][2],min(dp[i-2][0][0],dp[i-2][1][0])+1);	
		}
		dp[i][1][0]=min(dp[i][1][0],min(dp[i-1][1][1],dp[i-1][0][1])+1);
		dp[i][1][1]=min(dp[i][1][1],min({dp[i-1][1][0],dp[i-1][0][0],dp[i-1][0][2],dp[i-1][1][2]})+1);
		dp[i][1][2]=min(dp[i][1][1],min({dp[i-1][1][0],dp[i-1][0][0],dp[i-1][0][2],dp[i-1][1][2]})+1);
	}
//	cout<<dp[2][0][0]<<" ";
	int ans=1e9;
	for(int i=0;i<=1;i++){
		for(int j=0;j<=2;j++)
		{
			ans=min(ans,dp[n][i][j]);
		}
	}
	cout<<ans<<"\n";
}	
signed main()
{
	prs();
	std::ios::sync_with_stdio(false);
	cout.tie(0);cin.tie(0);
	int _=1;
//	cin>>_;
	while(_--)
	{
		solve();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 13956kb

input:

6
1 5 1 4 4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

9
30 6 7 12 15 8 20 17 14

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

1568
119 519 706 1003 1317 322 25 1466 816 525 1 1122 38 1511 774 515 274 780 647 230 1602 1051 810 1 1 1232 1 1202 1583 412 1111 168 309 1181 184 1260 491 764 809 1213 804 1470 1 1087 1235 1004 673 1338 1333 1392 1036 1539 268 1 712 727 297 404 1317 36 463 1067 1133 693 931 46 1 100 1608 965 1 1406...

output:

741

result:

wrong answer 1st numbers differ - expected: '733', found: '741'