Submission #319335

#	Time	Username	Problem	Language	Result	Execution time	Memory
319335		gustason	Lutrija (COCI19_lutrija)	C++14	70 / 70	342 ms	508 KiB

lutrija

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

map<int, ll> compress;
vector<ll> primes;
vector<int> adj[10];
bool visited[10], found = 0;
ll A, B;

bool isPrime(ll n) {
    if (n < 2) return false;
    for(ll i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}
void dfs(int v, vector<int> path) {
    path.push_back(v);
    if (compress[v] == B) {
        if (found) return;
        found = 1;
        cout << path.size() << "\n";
        for(int i : path) {
            cout << compress[i] << " ";
        }
        cout << "\n";
        return;
    }
    visited[v] = true;
    for(int u : adj[v]) {
        if (!visited[u]) {
            dfs(u, path);
        }
    }
    path.pop_back();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> A >> B;
    primes.push_back(A);
    primes.push_back(B);
    if (A != 2 && B != 2) primes.push_back(2);
    if (isPrime(A-2) && A-2 != B) {
        primes.push_back(A-2);
    }
    if (isPrime(A+2) && A+2 != B) {
        primes.push_back(A+2);
    }
    if (isPrime(B-2) && B-2 != A) {
        primes.push_back(B-2);
    }
    if (isPrime(B+2) && B+2 != A) {
        primes.push_back(B+2);
    }

    int n = primes.size();
    int id = 0, start = 0;
    for(ll i : primes) {
        if (i == A) start = id;
        compress[id++] = i;
    }

    for(int i = 0; i < n-1; i++) {
        for(int j = i+1; j < n; j++) {
            if (isPrime(abs(compress[i] - compress[j]))) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    vector<int> path;
    dfs(start, path);
    if (!found) {
        cout << -1;
    }
//    for(int i = 0; i < n; i++) {
//        cout << compress[i] << ":\n";
//        for(int u : adj[i]) {
//            cout << compress[u] << " ";
//        }
//        cout << "\n";
//    }
    return 0;
}
//~ check for overflows

• 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