oj.uz

Submission #160335

# Submission time Handle Problem Language Result Execution time Memory
160335 2019-10-27T03:03:53 Z model_code Lutrija (COCI19_lutrija) C++17
70 / 70
 642 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

const int MAXN = 10;

int bio[MAXN];

bool prosti(ll x) {
  if (x < 2) return 0;
  for (ll i = 2; i * i <= x; i++) {
    if (x % i == 0) return 0;
  }
  return 1;
}

ll a, b;

vector <ll> v;
vector <ll> rj, tmp;

void dfs(int cvor) {
  bio[cvor] = 1;
  tmp.pb(v[cvor]);
  if (v[cvor] == b) {
    if (rj.empty() || rj.size() > tmp.size()) rj = tmp;
    tmp.pop_back();
    return;
  }
  REP(i, (int)v.size()) {
    if (!bio[i] && prosti(max(v[i] - v[cvor], v[cvor] - v[i]))) {
      dfs(i);
      bio[i] = 0;
    }
  }
  tmp.pop_back();
}

int main() {
  cin >> a >> b;
  for (ll i = a - 2; i <= a + 2; i++) if (prosti(i)) v.pb(i);
  for (ll i = b - 2; i <= b + 2; i++) if (prosti(i)) v.pb(i);
  v.pb(2);

  sort(all(v));
  v.erase(unique(all(v)), v.end());

  REP(i, (int)v.size()) {
    if (v[i] == a) {
      bio[i] = 1;
      dfs(i);
    }
  }

  if (rj.empty()) puts("-1");
  else {
    printf("%d\n",(int)rj.size());
    for (auto t : rj) printf("%lld ", t);
    puts("");
  }
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 356 KB Output is correct
2 Correct 292 ms 504 KB Output is correct
3 Correct 480 ms 376 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 376 KB Output is correct
2 Correct 252 ms 376 KB Output is correct
3 Correct 351 ms 376 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 376 KB Output is correct
2 Correct 309 ms 376 KB Output is correct
3 Correct 319 ms 504 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 376 KB Output is correct
2 Correct 220 ms 376 KB Output is correct
3 Correct 117 ms 376 KB Output is correct