oj.uz

답안 #310158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310158 2020-10-06T02:06:42 Z LifeHappen__ Lutrija (COCI19_lutrija) C++14
42 / 70
 2000 ms 416 KB 
#include <bits/stdc++.h>

using namespace std;

#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 int 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 << ' ';
  }
}

Compilation message

lutrija.cpp:18:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+14' to '2147483647' [-Woverflow]
   18 | const int N = 1e14;
      |               ^~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2066 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2074 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2091 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -