제출 #198563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198563		alrad	Lutrija (COCI19_lutrija)	C++17	70 / 70	535 ms	504 KiB

lutrija

#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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7