oj.uz

Submission #237783

# Submission time Handle Problem Language Result Execution time Memory
237783 2020-06-08T18:14:44 Z DavidDamian Lutrija (COCI19_lutrija) C++11
70 / 70
 269 ms 43756 KB 
#include <bits/stdc++.h>
using namespace std;
///Sieve of Eratosthenes
///Graph Theory
///BFS
///Determine an array that has prime difference between any two adjacent elements
int sieve[10000007];
vector<int> primes;
void computeSieve()
{
    int n=1e7+1;
    for(int i=4;i<=n;i+=2){
        sieve[i]=1;
    }
    primes.push_back(2);
    for(int i=3;i<=n;i+=2){
        if(sieve[i]==1) continue;
        primes.push_back(i);
        for(int j=i+i;j<=n;j+=i){
            sieve[j]=1;
        }
    }
}
typedef long long ll;
bool isPrime(ll n)
{
    if(n<2) return false;
    for(int p: primes){
        if((ll)p*(ll)p > n) break;
        if(n%p==0) return false;
    }
    return true;
}
ll A,B;
int d[8];
ll number[8];
int color[8];
int p[8];
vector<int> adjList[8];
int k=3;
void dfs(int u)
{
    color[u]=1;
    for(int v: adjList[u]){
        if(color[v]==0){
            p[v]=u;
            d[v]=d[u]+1;
            dfs(v);
        }
    }
}
int main()
{
    computeSieve();
    cin>>A>>B;
    number[1]=B;
    number[2]=A;
    number[3]=2;
    if(isPrime(A-2)) number[++k]=A-2;
    if(isPrime(A+2)) number[++k]=A+2;
    if(isPrime(B-2)) number[++k]=B-2;
    if(isPrime(B+2)) number[++k]=B+2;
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k;j++){
            ll diff=abs(number[i]-number[j]);
            if(isPrime(diff)){
                adjList[i].push_back(j);
                adjList[j].push_back(i);
            }
        }
    }
    d[1]=1;
    dfs(1);
    if(d[2]==0){
        cout<<-1<<'\n';
        return 0;
    }
    cout<<d[2]<<'\n';
    int u=2;
    while(u!=1){
        cout<<number[u]<<" ";
        u=p[u];
    }
    cout<<number[1]<<'\n';
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 43624 KB Output is correct
2 Correct 218 ms 43624 KB Output is correct
3 Correct 210 ms 43624 KB Output is correct
4 Correct 223 ms 43752 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 43624 KB Output is correct
2 Correct 208 ms 43624 KB Output is correct
3 Correct 212 ms 43748 KB Output is correct
4 Correct 211 ms 43692 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 43624 KB Output is correct
2 Correct 214 ms 43752 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 43756 KB Output is correct
2 Correct 209 ms 43624 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 43748 KB Output is correct
2 Correct 209 ms 43628 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 43752 KB Output is correct
2 Correct 216 ms 43624 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 43724 KB Output is correct
2 Correct 239 ms 43704 KB Output is correct
3 Correct 237 ms 43728 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 43728 KB Output is correct
2 Correct 236 ms 43748 KB Output is correct
3 Correct 228 ms 43620 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 43728 KB Output is correct
2 Correct 235 ms 43696 KB Output is correct
3 Correct 246 ms 43624 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 43636 KB Output is correct
2 Correct 233 ms 43752 KB Output is correct
3 Correct 227 ms 43724 KB Output is correct