Submission #310159

# Submission time Handle Problem Language Result Execution time Memory
310159 2020-10-06T02:08:32 Z LifeHappen__ Lutrija (COCI19_lutrija) C++14
70 / 70
981 ms 504 KB
#include <bits/stdc++.h>

using namespace std;

#define int long long

#define ar array
#define fi first
#define se second
#define pb push_back
#define eb empalce_back
#define all(a) begin(a), end(a)

#define FOR(a, b, c) for (int64_t a = b, _c = c; a <= _c; ++a)
#define FORD(a, b, c) for (int64_t a = b, _c = c; a >= _c; --a)
#define FORV(a, b) for (auto &a : b)

using ll = long long;

const ll N = 1e14;

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  ll a, b;
  cin >> a >> b;
  auto chk = [&](ll x) {
    if(x < 2) return false;
    for (int i = 2; i * i <= x; ++i) {
      if(x % i == 0) return false;
    }
    return true;
  };
  vector <ll> lst;
  lst.pb(a); lst.pb(b); lst.pb(2);
  FOR(i, a - 2, a + 2) if(chk(i)) lst.pb(i);
  FOR(i, b - 2, b + 2) if(chk(i)) lst.pb(i);
  map<ll, vector<ll>> ad;
  map<ll, ll> pre, dd;
  FORV(v, lst) {
    FORV(u, lst) if(chk(labs(v - u))) {
      ad[v].pb(u);
    }
  }
  function<void(ll)> dfs=[&](ll u) {
    dd[u] = 1;
    FORV(v, ad[u]) if(!dd[v]) {
      pre[v] = u;
      dfs(v);
    }
  };
  dfs(a);
  if(!dd[b]) return cout << -1, 0;
  else {
    vector <ll> ans;
    ll now = b;
    while(now) {
      ans.pb(now);
      now = pre[now];
    }
    cout << ans.size() << '\n';
    reverse(all(ans));
    FORV(v, ans) cout << v << ' ';
  }
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 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
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 641 ms 376 KB Output is correct
2 Correct 432 ms 504 KB Output is correct
3 Correct 981 ms 504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 619 ms 384 KB Output is correct
2 Correct 426 ms 384 KB Output is correct
3 Correct 686 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 688 ms 384 KB Output is correct
2 Correct 429 ms 504 KB Output is correct
3 Correct 635 ms 504 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 505 ms 504 KB Output is correct
2 Correct 309 ms 504 KB Output is correct
3 Correct 224 ms 504 KB Output is correct