oj.uz

Submission #163353

# Submission time Handle Problem Language Result Execution time Memory
163353 2019-11-12T18:54:08 Z dolphingarlic Lutrija (COCI19_lutrija) C++14
70 / 70
 978 ms 508 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<ll> stck;
map<ll, bool> visited;
ll a, b;
bool found = false;

bool is_prime(ll n) {
    if (n < 2) return false;
    FOR(i, 2, sqrt(n) + 1) if (n % i == 0) return false;
    return true;
}

void dfs(ll node) {
    if (found) return;
    stck.push_back(node);
    visited[node] = true;

    if (node == b) {
        cout << stck.size() << '\n';
        for (ll i : stck) cout << i << ' ';
        found = true;
        return;
    }

    if (is_prime(node + 2) && !visited[node + 2]) dfs(node + 2);
    if (is_prime(node - 2)) {
        if (!visited[node - 2]) dfs(node - 2);
        if (!visited[2]) dfs(2);
    }
    if (is_prime(b - node)) dfs(b);
    if (is_prime(b - 2) && is_prime(b - node - 2)) dfs(b - 2);
    if (is_prime(b + 2) && is_prime(b - node + 2)) dfs(b + 2);
    stck.pop_back();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b;

    dfs(a);
    if (!found) cout << -1;
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 2 ms 252 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 978 ms 376 KB Output is correct
2 Correct 126 ms 376 KB Output is correct
3 Correct 245 ms 380 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 376 KB Output is correct
2 Correct 124 ms 376 KB Output is correct
3 Correct 180 ms 376 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 859 ms 508 KB Output is correct
2 Correct 123 ms 412 KB Output is correct
3 Correct 167 ms 376 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 384 KB Output is correct
2 Correct 92 ms 380 KB Output is correct
3 Correct 62 ms 504 KB Output is correct