제출 #1146619

#제출 시각아이디문제언어결과실행 시간메모리
1146619mnbvcxz123Lutrija (COCI19_lutrija)C++20
70 / 70
647 ms1864 KiB
#include <bits/stdc++.h>
using namespace std;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mxN = 2e5 + 5, L = 20, mxA = 1e15 + 35;

bool isprime(intt n) {
    if(n == 1) return false;
    for(int i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) return false;
    }
    return true;
}

vector<vector<intt>>graph;
vector<intt> visited(mxN, 0), path, v(8);
bool ok = false;

void dfs(intt u, intt end) {
    visited[u] = true;
    path.pb(u);

    if (u == end) {
        ok = true;
        vector<intt>actans;
        for(int i = 0; i < path.size(); i++) {
            if(i < path.size() - 1 && v[path[i]] == v[path[i+1]]) {
                continue;
            }
            actans.pb(v[path[i]]);
        }
        cout << actans.size() << endl;
        for(intt i : actans) cout << i << " ";
        cout << endl;
        return;
    } else {
        for (intt v : graph[u]) {
            if (!visited[v]) {
                dfs(v, end);
            }
        }
    }
  
    
    path.pop_back();
    visited[u] = false;
}

void solve() {
    intt l,r, li =0, ri = 0;
    cin >> l >> r;
    v = {-mxA, 2ll, l - 2, r - 2, l, r, l + 2, r + 2};
    sort(ALL(v));
    
    graph.resize(8);
    for(intt i = 1; i <= 7; i++) {
        if(v[i] == l) li = i;
        if(v[i] == r) ri = i;
        for(intt j = i + 1; j <= 7; j++) {
            if(isprime(v[i]) && isprime(v[j]) && isprime(abs(v[i]-v[j])) && v[i] && v[j]){
                graph[i].pb(j);
                graph[j].pb(i);
            }
        }
    }
    dfs(li, ri);
    if(!ok || path.size() == 0) {
      cout << -1 << endl;
    }
}

int main() {
    SPEED;
    int tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...