QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#712581#7624. Mystery of PrimeTANGTANGCCWA 3ms6224kbC++231.9kb2024-11-05 16:15:092024-11-05 16:15:10

Judging History

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

  • [2024-11-05 16:15:10]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:6224kb
  • [2024-11-05 16:15:09]
  • 提交

answer

//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define int long long
#define ld long double
#define i32 int
#define u32 unsigned int
#define i64 long long
#define u64 unsigned long long
#define u27 __int128
#define endl '\n'
#define VI vector<int>
#define VVI vector<VI>
#define rand() RANDOM(GEN)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define CTM (cout<<"Time:"<<static_cast<double>(clock()-START_TIME)/CLOCKS_PER_SEC*1000<<"ms"<<endl)
typedef long long ll;

using namespace std;
random_device SEED;
mt19937_64 GEN(SEED());
uniform_int_distribution<u64> RANDOM(0, numeric_limits<u64>::max());
const clock_t START_TIME = clock();
const int N=1e5+50,M=2e5;
bool f[M+50];
int sz[N],dp[N][3];
signed main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    IO;
    for (int i = 2; i <= M; ++i) {
        for (int j = 2*i; j <= M; j+=i) {
            f[j]=1;
        }
    }
    int n;
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        cin>>sz[i];
    }
    memset(dp,127,sizeof(dp));
    dp[1][0]=0,dp[1][1]=dp[1][2]=1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) {
            if(!f[sz[i]+sz[i-1]]) {
                dp[i][0]=min(dp[i][0],dp[i-1][0]);
            }
            if(!f[1+sz[i-1]]) {
                dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
            }
            if(!f[2+sz[i-1]]) {
                dp[i][2]=min(dp[i][2],dp[i-1][0]+1);
            }
            if(!f[1+sz[i]]) {
                dp[i][0]=min(dp[i][0],dp[i-1][1]);
            }
            if(!f[2+sz[i]]) {
                dp[i][0]=min(dp[i][0],dp[i-1][2]);
            }
            dp[i][1]=min({dp[i][1],dp[i-1][1]+1,dp[i-1][2]+1});
            dp[i][2]=min({dp[i][2],dp[i-1][1]+1});
        }
    }
    cout<<min({dp[n][0],dp[n][1],dp[n][2]});
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 6224kb

input:

6
1 5 1 4 4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 6204kb

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: 3ms
memory: 6220kb

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:

1020

result:

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