# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
217597 | bayemirov | Lutrija (COCI19_lutrija) | C++17 | 771 ms | 508 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//bayemirov
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define pb push_back
const ll INF = 1e9;
const int d[] = {0, 2, -2};
map<ll, ll> dist, p;
map<ll, vector<ll>> adj;
vector<ll> v = {2};
ll a, b;
bool isPrime(ll x) {
if (x < 2) return 0;
for (ll i = 2; i * i <= x; i++)
if (x % i == 0)
return 0;
return 1;
}
void bfs() {
for (auto x : v) dist[x] = INF;
dist[a] = 0;
queue<ll> q;
q.push(a);
while (!q.empty()) {
ll v = q.front();
q.pop();
for (auto to : adj[v]) {
if (dist[to] > dist[v] + 1) {
dist[to] = dist[v] + 1;
p[to] = v;
q.push(to);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> a >> b;
for (int i = 0; i < 3; i++) {
if (isPrime(a+d[i])) v.pb(a+d[i]);
if (isPrime(b+d[i])) v.pb(b+d[i]);
}
for (int i = 0; i < v.size(); i++)
for (int j = 0; j < v.size(); j++)
if (isPrime(abs(v[i]-v[j])))
adj[v[i]].pb(v[j]);
bfs();
if (dist[b] == INF) cout << -1, exit(0);
p[a] = -1;
vector<ll> ans;
while (b != -1) {
ans.pb(b);
b = p[b];
}
reverse(ans.begin(), ans.end());
cout << ans.size() << "\n";
for (auto x : ans) cout << x << ' ';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |