oj.uz

답안 #299239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299239 2020-09-14T15:22:52 Z ryuku1110 Lutrija (COCI19_lutrija) C++14
70 / 70
 863 ms 512 KB 
#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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 791 ms 504 KB Output is correct
2 Correct 426 ms 376 KB Output is correct
3 Correct 857 ms 384 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 774 ms 376 KB Output is correct
2 Correct 388 ms 380 KB Output is correct
3 Correct 617 ms 384 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 863 ms 508 KB Output is correct
2 Correct 427 ms 384 KB Output is correct
3 Correct 568 ms 384 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 623 ms 384 KB Output is correct
2 Correct 310 ms 384 KB Output is correct
3 Correct 210 ms 376 KB Output is correct