제출 #344554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
344554		limabeans	Lutrija (COCI19_lutrija)	C++17	70 / 70	574 ms	620 KiB

lutrija

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;



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



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    assert(isprime(41));

    ll a,b;
    cin>>a>>b;

    //0->2->1->0->2->0.. mod3

    map<ll,vector<ll>> g;
    vector<ll> tmp = {a-2,a,a+2,b-2,b,b+2,2};
    vector<ll> nodes;
    for (ll x: tmp) {
	if (isprime(x)) {
	    nodes.push_back(x);
	}
    }
    
    for (int i=0; i<(int)nodes.size(); i++) {
	for (int j=i+1; j<(int)nodes.size(); j++) {
	    ll x = nodes[i];
	    ll y = nodes[j];
	    if (isprime(abs(x-y))) {
		g[x].push_back(y);
		g[y].push_back(x);
	    }
	}
    }


    map<ll,ll> par;

    queue<ll> qq;
    qq.push(a);
    while (qq.size()) {
	ll at = qq.front();
	qq.pop();
	for (ll to: g[at]) {
	    if (!par.count(to)) {
		par[to] = at;
		qq.push(to);
	    }
	}
    }


    if (!par.count(b)) out(-1);
    vector<ll> path;
    while (b != a) {
	path.push_back(b);
	b = par[b];
    }
    path.push_back(a);

    cout<<path.size()<<"\n";
    while (path.size()) {
	cout<<path.back()<<" ";
	path.pop_back();
    }
    cout<<endl;
    
    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