oj.uz

Submission #198559

# Submission time Handle Problem Language Result Execution time Memory
198559 2020-01-26T15:33:49 Z alrad Lutrija (COCI19_lutrija) C++17
0 / 70
 363 ms 396 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100;

long long a , b;
vector<long long> primes;

bool isPrime(long long x) {
   if (x < 2) {
      return false;
   }
   for (long long i = 2; i <= sqrt(x); i++) {
      if (x % i == 0) {
         return false;
      }
   }
   return true;
}

vector<vector<int> > g(N , vector<int>());
vector<bool> used(N , false);
vector<long long> ans;

void dfs(int v) {
   used[v] = true;
   if (primes[v] == b) {
      cout << (int)ans.size() << '\n';
      for (long long cur : ans) {
         cout << cur << " ";
      }
      cout << '\n';
      exit(0);
   }
   for (int to : g[v]) {
      if (!used[to]) {
         ans.push_back(primes[to]);
         dfs(to);
         ans.pop_back();
      }
   }
}

int main() {
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   cin >> a >> b;
   for (long long i = a - 2; i <= a + 2; i++) {
      if (isPrime(i)) {
         primes.push_back(i);
      }
   }
   for (long long i = b - 2; i <= b + 2; i++) {
      if (isPrime(i)) {
         primes.push_back(i);
      }
   }
   sort(primes.begin() , primes.end());
   primes.erase(unique(primes.begin() , primes.end()) , primes.end());
   for (int i = 0; i < (int)primes.size(); i++) {
      for (int j = i + 1; j < (int)primes.size(); j++) {
         if (isPrime(primes[j] - primes[i])) {
            g[i].push_back(j);
            g[j].push_back(i);
         }
      }
   }
   for (int i = 0; i < (int)primes.size(); i++) {
      if (primes[i] == a) {
         ans.push_back(a);
         dfs(i);
         break;
      }
   }
   cout << -1 << '\n';
   return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 338 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 325 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 363 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 264 ms 396 KB Output isn't correct
2 Halted 0 ms 0 KB -