Submission #205341

#	Time	Username	Problem	Language	Result	Execution time	Memory
205341		mraron	Lutrija (COCI19_lutrija)	C++14	42 / 70	182 ms	376 KiB

lutrija

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool ip(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() {
	ll a,b;
	cin>>a>>b;
	vector<ll> lst;
	lst.push_back(a);
	lst.push_back(b);
	lst.push_back(2);
	if(ip(a-4)) lst.push_back(a-4);	
	if(ip(a-2)) lst.push_back(a-2);	
	if(ip(a+2)) lst.push_back(a+2);
	if(ip(a+4)) lst.push_back(a+4);
	if(ip(b-4)) lst.push_back(b-4);	
	if(ip(b-2)) lst.push_back(b-2);	
	if(ip(b+2)) lst.push_back(b+2);
	if(ip(b+4)) lst.push_back(b+4);
	map<ll,ll> par;
	par[a]=0;
	queue<ll> q;
	q.push(a);
	while(!q.empty()) {
		int fr=q.front();
		q.pop();
		for(auto i:lst) {
			if(ip(abs(fr-i)) && par.count(i)==0) {
				par[i]=fr;
				q.push(i);
			}
		}
	}
	
	if(par.count(b)!=0) {
		vector<ll> ans;
		while(b>0) {
			ans.push_back(b);
			b=par[b];
		}
		reverse(ans.begin(),ans.end());
		cout<<ans.size()<<"\n";
		for(auto i:ans) cout<<i<<" ";
		cout<<"\n";
	}else cout<<"-1\n";
}

• 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: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7