oj.uz

Submission #313628

# Submission time Handle Problem Language Result Execution time Memory
313628 2020-10-16T12:20:34 Z YJU Lutrija (COCI19_lutrija) C++14
70 / 70
 864 ms 504 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
int t = 0;
bool visit[30];
ll arr[30], a, b;
vector <int> adj[30];
 
bool prime(ll x) {
    if (x < 2) return false;
    for (ll i = 2; i <= sqrt(x); ++ i) 
        if (x % i == 0) return false;
    return true;
}
int par[30];
vector <ll> ans;
 
void dfs(int u) {
    visit[u] = true;
    for (int v : adj[u]) {
        if (visit[v]) continue;
        if (prime(abs(arr[u] - arr[v]))) {
            par[v] = u;
            dfs(v);
        }
    }
}
 
int main() {
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> a >> b;
    
    ++ t;
    arr[t] = a;
    ++ t;
    arr[t] = b;
 
    for (ll i = a - 2; i <= a + 2; ++ i) {
        if (prime(i) && i != a) {
            ++ t;
            arr[t] = i;
        }
    }
    for (ll i = b - 2; i <= b + 2; ++ i) {
        if (prime(i) && i != b) {
            ++ t;
            arr[t] = i;
        }
    }
    ++ t;
    arr[t] = 2;
 
    for (int i = 1; i <= t; ++ i) {
        for (int j = 1; j <= t; ++ j) {
            if (i != j && prime(abs(arr[i] - arr[j]))) {
                adj[i].pb(j);
                adj[j].pb(i);
            }
        }
    }
 
    dfs(1);
    if (!visit[2]) {
        cout << -1;
        return 0;
    }
    ans.pb(2);
    int pivot = 2;
    while (par[pivot] != 0) {
        ans.pb(par[pivot]);
        pivot = par[pivot];
    }
    cout << ans.size() << endl;
    for (int i = ans.size() - 1; i >= 0; -- i) {
        cout << arr[ans[i]] << " ";
    }
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 504 KB Output is correct
2 Correct 421 ms 504 KB Output is correct
3 Correct 858 ms 388 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 504 KB Output is correct
2 Correct 387 ms 384 KB Output is correct
3 Correct 622 ms 384 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 384 KB Output is correct
2 Correct 426 ms 384 KB Output is correct
3 Correct 570 ms 384 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 504 KB Output is correct
2 Correct 308 ms 384 KB Output is correct
3 Correct 202 ms 504 KB Output is correct