제출 #163353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163353		dolphingarlic	Lutrija (COCI19_lutrija)	C++14	70 / 70	978 ms	508 KiB

lutrija

#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 / 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