oj.uz

Submission #319335

# Submission time Handle Problem Language Result Execution time Memory
319335 2020-11-04T21:17:37 Z gustason Lutrija (COCI19_lutrija) C++14
70 / 70
 342 ms 508 KB 
#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.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 484 KB Output is correct
2 Correct 191 ms 508 KB Output is correct
3 Correct 288 ms 484 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 484 KB Output is correct
2 Correct 187 ms 492 KB Output is correct
3 Correct 207 ms 364 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 484 KB Output is correct
2 Correct 178 ms 364 KB Output is correct
3 Correct 190 ms 484 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 364 KB Output is correct
2 Correct 139 ms 484 KB Output is correct
3 Correct 69 ms 364 KB Output is correct