제출 #344550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
344550		limabeans	Lutrija (COCI19_lutrija)	C++17	0 / 70	173 ms	492 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) {
    for (ll i=2; i*i<=x; i++) {
	if (x%i==0) return false;
    }
    return true;
}



void solve(ll a, ll b, bool rev=false) {
    map<ll,ll> par;
    par[a] = -1;
	
    queue<ll> qq;
    qq.push(a);
    while (qq.size()) {
	ll at = qq.front();
	qq.pop();
	if (isprime(abs(at-b))) {
	    par[b] = at;
	    break;
	}
	for (ll dx: {-2,2}) {
	    ll to = dx+at;
	    if (par.count(to)) continue;
	    if (to>1 && isprime(to)) {
		par[to] = at;
		qq.push(to);
	    }
	}
	
    }

    if (!par.count(b)) {
	return;
    }

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

    path.push_back(b);

    if (rev) reverse(path.begin(), path.end());

    cout<<path.size()<<"\n";
    while (path.size()) {
	cout<<path.back()<<" ";
	path.pop_back();
    }
    cout<<endl;
    exit(0);
}

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


    assert(isprime(41));

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

    if (isprime(abs(a-b))) {
	cout<<"2\n";
	cout<<a<<" "<<b<<"\n";
	exit(0);
    }

    solve(a,b);
    solve(b,a,true);

    out(-1);


    
    
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 7
• Subtask 5: 0 / 7
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7