oj.uz

Submission #198563

# Submission time Handle Problem Language Result Execution time Memory
198563 2020-01-26T15:37:12 Z alrad Lutrija (COCI19_lutrija) C++17
70 / 70
 535 ms 504 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);
      }
   }
   primes.push_back(2);
   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
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
7.0 / 7.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 504 KB Output is correct
2 Correct 343 ms 376 KB Output is correct
3 Correct 498 ms 376 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 376 KB Output is correct
2 Correct 311 ms 504 KB Output is correct
3 Correct 368 ms 504 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 504 KB Output is correct
2 Correct 354 ms 380 KB Output is correct
3 Correct 331 ms 376 KB Output is correct

Subtask #10
7.0 / 7.0

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