Submission #313628

#	Time	Username	Problem	Language	Result	Execution time	Memory
313628		YJU	Lutrija (COCI19_lutrija)	C++14	70 / 70	864 ms	504 KiB

lutrija

#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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7