oj.uz

Submission #1090042

# Submission time Handle Problem Language Result Execution time Memory
1090042 2024-09-17T16:00:53 Z Hora000 Lutrija (COCI19_lutrija) C++14
70 / 70
 852 ms 412 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;

    //ofstream cout("c.out"); 
vector<vector<int>> g;

bool prim(long long x){
    if(x <= 1) return false;
    for(long long i = 2; i <= sqrt(x); i++){
        if(x % i == 0) return false;
    }
    return true;
}

vector<long long> bfs(int v){
    vector<bool> vis(7);
    queue<int> q;
    vector<int> p(7, -1);
    q.push(v);
    vis[v] = true;
    while(!q.empty()){
        for(auto x : g[q.front()]){
            if(!vis[x]){
                vis[x] = true;
                p[x] = q.front();
                q.push(x);
            }
        }
        q.pop();
    }
    if(p[6] == -1) return {(long long)-1};
    vector<long long> r;
    int c = 6;
    while(p[c] != -1){
        r.push_back(c);
        c = p[c];
    }
    r.push_back(c);
    reverse(r.begin(), r.end());
    return r;
}

int main(){
    //ifstream cin("c.in"); 
    long long a, b;
    cin >> a >> b;
    g.resize(7);
    //0 a, 1 a + 2, 2 a - 2, 3 2, 4 b - 2, 5 b + 2, 6 b
    vector<long long> e = {a, a + 2, a - 2, 2, b - 2, b + 2, b};
    for(int i = 0; i < 7; i++){
        for(int j = 0; j < 7; j++){
            if(prim(abs(e[i] - e[j])) && prim(e[i]) && prim(e[j])){
                g[i].push_back(j);
            }
        }
    }
    vector<long long> ans = bfs(0);
    if(ans[0] == -1) cout << "-1\n";
    else{
        cout << ans.size() << "\n";
        for(auto x : ans) cout << e[x] << " ";
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 408 KB Output is correct
2 Correct 363 ms 348 KB Output is correct
3 Correct 852 ms 408 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 412 KB Output is correct
2 Correct 270 ms 348 KB Output is correct
3 Correct 624 ms 344 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 348 KB Output is correct
2 Correct 326 ms 348 KB Output is correct
3 Correct 572 ms 344 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 404 KB Output is correct
2 Correct 228 ms 344 KB Output is correct
3 Correct 209 ms 412 KB Output is correct